[Python][이코테] 큰 수의 법칙

조건

• 첫째 줄에 N (2 ≤ N ≤ 1000), M (1 ≤ M ≤ 10000), K(1 ≤ K ≤ 10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다

 

입력 예시

5 8 3
2 4 5 4 6

출력 예시

46

 

주어진 배열에서 가장 큰 수를 K번 더하고 그 다음 큰 수를 더하고 또 그다음 가장 큰 수를 K번 더하는걸

 

모두 합쳐 M번 더하는 큰 수의 법칙이다.

 

즉, 가장 큰 수를 K번 더하고 두번째로 큰 수를 한 번 더하는 방식이다.

 

간단한 방법으로는

 

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

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

result = 0

while True:
    for i in range(k):
        if(m == 0):
            break
        result += first
        m -= 1
    
    if(m==0):
        break
    
    result += second
    m -= 1
    
print(result)

위의 방법이 있으나

 

위는 while문과 for문의 두번의 반복문이 있어

O(N^2)의 시간이 걸리는 비효율적인 알고리즘이라 할 수 있다.

 

이를 단순하게 수식으로만 계산한다면

 

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()

first = data[n-1]
second = data[n-2]

#가장 큰 수가 더해지는 횟수 계산
count = int(m / (k+1) * k)
count += m% (k+1)

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

print(result)

위의 방식은 단순 계산식만 있기에

 

O(1)의 시간이 소요된다.

 

위의 식이 도출된 과정은

 

위의 입력 예시를 토대로 풀어보자면

 

[2, 4, 5, 4 ,6]의 배열에서 

 

가장 큰 수 6

두 번째로 큰 수 5

 

총 8번 연산

 

가장 큰 수 6을 3번 더하고 두 번째로 큰 수 5를 한번 더함

(6 + 6 + 6 + 5) + (6 + 6 + 6 + 5)

의 공식이 완성된다.

 

즉 가장 먼저 반복되는 (6 + 6 + 6 + 5) 는 K + 1 개의 하나의 수열이 되며

 

M을 (K + 1)로 나눈 몫이 수열의 반복 횟수가 된다. 그 후 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다.

 

이를 정리하면 (M / (K + 1)) * K

 

하지만 .M이 K + 1 로 깔끔히 나눠지지 않은 경우도 생각하면 M을 (K + 1)로 나눈 나머지를 더해주면 된다.

 

즉 M % (K + 1)이 되며 이를 위의 식과 합치면

 

(M / (K + 1)) * K + M % (K + 1)

 

로 정의할 수있다.

 

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

result = count * first

가장 큰 수를 구하는 코드는 위와 같으며

 

두 번째로 큰 수를 더하는 방법은

 

result += (m-count) * second

M에서 가장 큰 수의 회수를 뺀 횟수 * 두 번째로 큰 수 를 하면 구할 수 있다.