[이코테] 큰 수의 법칙

문제

동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다. 

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정한다. 예를 들어 순선대로 2, 4, 5, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 +6 +5인  46이 된다.

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이가능하다. 결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4인 28이 도출된다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오. 

입력 조건

1. 첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.

2. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.

3. 입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

출력 조건

첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

입력 예시

5 8 3

2 4 5 4 6

출력 예시

46

 

내가 작성한 코드

import sys
N, M, K = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))

num = sorted(num)
first = num[-1]
second = num[-2]
sum = 0
for i in range(M):
    if i != 0 and i % K == 0:
        sum += second
    else: 
        sum += first
    
print(sum)

평소엔 제일 큰 수(first)를 더하다가,

제일 큰 수를 K번 더했다는 것은 i를 K로 나눈 나머지가 0이라는 것이다.
이 때는 두 번째로 큰 수(second)를 더해준다.

하지만 이건 시간복잡도 측면에서 봤을 때 모범답안이 되지 못한다.
M번 만큼 반복문을 돌기 때문에 M이 크다면 비효율적인 코드이다. (O(M))

 

책 답안 코드 1

# 입력 부분 생략

data.sort()
first = data[n-1]
second = data[n-2]
result = 0

while True:
    for i in range(K):  # K번 가장 큰 수를 더함
        if M == 0:
            break
        result += first
        M -= 1
    if M == 0:
        break
    result += second  # 한 번 두 번째 큰 수를 더함
    M -= 1
    
print(result)

내 코드의 for문이나 1번 답안 코드의 while문이나
O(M)의 복잡도를 가지기 때문에 똑같은 코드라 보면 될 것 같다.

 

책 답안 코드 2

# 윗 부분 생략

count = int(m / (k+1)) * k
count += m % (k + 1)

result = 0
result += (count) * first
result += (m - count) * second

print(result)

이 답안은 수학적으로 접근한 답안이다.

문제의 입출력 예시처럼 M=8, K=3, 입력수열=[2, 4, 5, 4, 6] 이라면,
제일 큰 수 6을 K번 더하고, 5를 더하고 ... 즉 {6, 6, 6, 5}가 M번 까지 반복되는 것의 합이 정답이다.
반복되는 수열은 (K+1) 의 길이를 가지게 되고, M(총 덧셈 횟수)을 (K+1)로 나눈 몫이 총 수열 반복 횟수가 된다.
==> 1️⃣ M / (K+1)

여기에 K를 곱하면 가장 큰 수가 등장하는 횟수가 된다.
==> 2️⃣ ( M / (K+1) ) * K

M이 (K+1)로 나누어떨어지지 않는 경우에는,
M을 (K+1)로 나눈 나머지만큼 가장 큰 수가 더해지는 것까지 고려해야한다.
==> 3️⃣ ( M / (K+1) ) * K + M % (K + 1)

 

문제를 보고 단 번에 떠오르지 않으면 공책을 꺼내 써보면서 로직을 파악하기 위해 노력하는데,
아직 나는 이 수학적 접근법까지 떠올리기엔 많이 부족한 실력인 것 같다.

꾸준히 하다보면 충분히 향상될 수 있는 부분이라 생각한다.