[그리디 알고리즘] 큰 수의 법칙 - 파이썬(python)

큰 수의 법칙 (11399번)

난이도 : 下 풀이 시간 : 30분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

n, m, k = map(int, input().split())
array = list(map(int, input().split()))
count = 0

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

while True:
    if (m == 0):
        break

    else:
        for i in range(k):
            count = count + first
            
            if (m == 0):
                break

            m = m - 1

        count = count + second
        
        m = m - 1

print(count)

---

예시

 

# N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백을 기준으로 구분하여 입력 받기
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을 하나씩 줄여나간다는 점입니다.
답을 입력받을 변수 count를 선언하고, 규칙에 따라 first, second를 더해줍니다.
한 번 더할 때 마다 m을 1씩 줄이고, m이 0이 되면 반복문을 종료하도록 합니다.