[이것이 코딩 테스트다]큰 수의 법칙

문제

동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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

 

 

---

그리디 알고리즘 문제로 '탐욕법'으로 소개됩니다.

그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'입니다.

 

01 내가 작성한 답안

n, m, k = map(int, input().split(' '))
num_list = list(map(int, input().split(' ')))
result = 0
count = 0

num_list.sort()
num_list = num_list[-2:]

for i in range(m):
    if count < k:
        result += num_list[-1]
        count += 1
    elif num_list[-1] == num_list[-2]:
        result += num_list[-1]
        if i % k == k-1:
            count = 0
    else:
        result += num_list[-2]
        count = 0

print(result)

k를 활용할 수 있었는데 count변수를 따로 설정한게 아쉬웠다.

답안에 비해 상당히 지저분하게 작성했는데, 답안을 보면서 정리해야겠다.

 

02 

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

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

result = 0

while True:
    for i in range(k):
        if m == 0: # m이 0이라면 반복문 탈출
            break
        result += first
        m -= 1
    if m == 0:
        break
    result += second
    m -= 1

print(result)

 

03 간략한 풀이

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

num.sort(reverse=True)
first = num[0]
second = num[1]

count = (m//(k+1))*k + m%(k+1)
result = first*count + second*(m-count)
print(result)