[나동빈 파이썬/그리디-①] 큰 수의 법칙

큰 수의 법칙

 

민지's 문제요약

M회를 더해야하는데, 같은 원소를 K번 이상 연속해서 사용할 수는 없음.

다른 원소 한 번 더했다가 다시 돌아가는건 오케이.

같은 숫자가 있어도 인덱스가 다르면 다른 숫자로 취급함.

 

민지's 아이디어

1. 내림차순으로 정렬한다.

2. 반복가능한 K만큼 가장 큰 수를 반복해서 더한다.

(M회가 채워지면 끝이고, 안 채워지면 3단계 수행)

3. 두 번째로 큰 수를 한 번 더한다.

(M회가 채워지면 끝이고, 안 채워지면 다시 2번으로 돌아간다.)

 

N, M, K = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort(reverse=True)

result = 0
for _ in range(M):
    for _ in range(K):
        result += nums[0]
        M -= 1
        if M==0:
            break
    result += nums[1]
    M -= 1
    if M==0:
        break

print(result)

 

수열의 길이 N의 값이 뭐든 간에 어차피 쓰이는 값은 가장 큰 수, 그리고 그 다음으로 큰 수 이렇게 두 개뿐이다.

더하는 횟수가 M 미만일 때, 가장 큰 수를 K번만큼 더하고 두 번째로 큰 수를 1번 더하고 다시 가장 큰 수를 더하고... 이런 방식으로 그리디하게 해결 할 수 있다.

 

tip: 수학적으로도 해결해보자