그리디 1-2) 큰 수의 법칙

실전 1. 큰수의 법칙

문제 해설

이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다.

# 큰수의 법칙
def maxNum(n, m, k, listNum):
    result = 0
    listNum.sort()
    max1 = listNum[-1]
    max2 = listNum[-2]
    q = 1
    while True:
        if m == 0:
            break
        maxN = max(listNum)
        for t in range(k):
            if m == 0:
                break
            print(max1)
            result += max1
            m -= 1
        print(max2)    
        result += max2
        m -= 1
    return result
print(maxNum(5,8,3,[2,4,5,4,6]))

이 문제는 반복되는 수열에 대해서 파악해야 한다.  

수열을 파악해서 가장 큰 수가 더해지는 횟수의 식을 구해서 풀 수도 있다.

위의 식을 이용하여 가장 큰 수가 더해지는 횟수를 구한 다음, 이를 이용해 두 번째로 큰 수가 더해지는 횟수까지 구할 수 있다. 코드는 아래와 같다.

• 더 간단한 코드

# N, M, K를 공백으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력 받기
data = list(map(int, input().split()))

# 입력 받은 수 정렬
data.sort() 

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

result = 0
result += count * data[-1] # 가장 큰 수 더하기
result += (m-count) * data[-2] # 두 번째로 큰 수 더하기

print(result) # 최종 답안 출력