[이취코] 큰 수의 법칙

출처 : 이것이 취업을 위한 코딩 테스트다 with python p.92

 

---

1. 문제

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

(단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다)

 

예시

5 8 3 # N,M,K
2 4 6 4 6

예시 출력

46

 

2. 내 코드

N, M, K = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
max1, max2 = data[-1], data[-2]

_list = M * [max1]
for i in range(K,M,K+1):
    _list[i] = max2

print(sum(_list))

 _list에 최종적으로 더할 숫자들을 넣어주었다. 처음에는 가장 큰 값으로만 _list를 채우고 큰 수의 법칙에 따라 같은 숫자가 연속해서 K번을 초과하지 않도록 제한을 걸었다. 즉, 인덱스차가 K+1이 되도록 해서, K, 2K+1,3K+2...번째 값을 두 번째로 큰 수로 바꿨다.

 

3. 풀이1

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): # 가장 큰 수를 K번 더하기
       if m == 0:
             break
        result += first
        m -= 1 # 수를 하나씩 더하면 m의 개수를 하나씩 줄이기
     
    if m == 0:
    	break
    result += second
    m -= 1
    
print(result)

가장 큰 수(first) : O

두 번째로 큰 수(second) : X

K를 3이라고 했을 때, O(+first)O(+first)O(+first)X(+second)O(+first)O(+first)O(+first)X(+second) 이런 식으로 구현했다.

 

OOOXOOOX

first+first+first+second+first+first+first+second

 

4. 풀이 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 = 0
result += (count) * first
result += (m-count) * second

print(result)

 

① M이 K+1로 나누어 떨어지는 경우

    M을 (k+1)으로 나눈 몫에 K를 곱함 = 가장 큰 수가 등장하는 횟수

 

② M이 K+1로 나누어 떨어지지 않는 경우

    ①에서 구한 값 + M을 (k+1)을 나눈 나머지

 

⇒ 가장 큰 수 k번 + 두번째로 큰 수 1번

 

따라서 가장 큰 수가 더해지는 횟수 = int(M / (K+1)) * K + M % (K+1) * 1