[Algorithm] 03. 그리디 : (2) 큰 수의 법칙

문제

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만들어라

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

배열의 크기 N, 숫자가 더해지는 횟수 M, 연속으로 더할 수 있는 횟수 K에 따른 큰 수를 출력하라

 

입력조건

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

출력조건

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

 

 

내 풀이

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

array.sort(reverse=True) # 입력받은 배열을 내림차순으로 배열

print(array)
 
first = array[0] # 가장 큰 수
second = array[1] # 두번째로 큰 수

countM = 0 # 숫자를 M번까지 더할 수 있으므로 세줘야 함
countK = 0 # 같은 수를 연속으로 K번까지만 더할 수 있으므로 세줘야 함
sum = 0 # 합

while countK < K: # 가장 큰 수를 K번까지만 더하는 반복문
    if countM < M: # 숫자가 더해지는 횟수가 M번보다 작을 때까지만 위 while문을 반복
        countM += 1
        countK += 1
        sum += first
        if countK == K: # 만약 같은 수를 K번까지 더하면
            sum += second # 두번째로 큰 수를 더해야 함
            countK = 0 # K를 0으로 리셋하여 다시 셈
            countM += 1
            continue
    else: # 숫자가 더해지는 횟수가 M번이 되었을 때 while문을 종료함
        break

print(sum)

어떻게 작성해야 할지 감은 왔는데 반복문으로 표현하는 게 조금 힘들었다

continue break 개념에 대해 더 공부해야 될 것 같다😢

 

 

문제풀이 (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):
        if M == 0:
            break
        result += first
        M -= 1
    if M ==0:
        break
    result += second
    M -= 1

print(result)

숫자를 더할 때마다 M을 1씩 빼는 아이디어가 새로웠다

 

 

문제 풀이 (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는 가장 큰 수를 더하는 횟수이다
# k+1은 수열의 주기이다
count = int( M / (K+1) ) * K # M이 주기의 배수일 때 더해지는 횟수 
count += M % (K+1) # M이 주기에 나누어 떨어지지 않았을 때도 포함

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

print(result)

수열을 이용한 풀이이다