[코테 공부] 그리디 알고리즘(탐욕법 Greedy Algorithm)_1

현재 상황에서 지금 당장 좋은 것만 골라라!

• 매 순간 가장 좋아보이는 것을 선택한다.
• 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.
• 100%의 최적해를 알려주지 않는다. (최적이 아닌 / '적당히~ 괜찮은 방법'을 찾을 때 좋음)

문제 내에서 '가장 큰 순서대로', '가장 작은 순서대로'처럼
알게 모르게 기준을 제시해주는 경우가 있다.
ex) 거스름돈 계산

큰 수의 법칙

• 다양한 수로 이루어진 배열이 있을 때
• 주어진 수를 M 번 더하여 가장 큰 수를 만드는 법칙
• 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K 번을 초과할 수 없음

실전 문제

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때
큰 수의 법칙에 따라 더해진 답을 출력한다.

첫째 줄에 N (2이상 1,000이하), M (1이상 10,000이하), K (1이상 10,000이하)의 자연수가 주어지며 각 자연수는 공백으로 구분한다.
둘째 줄에 N개의 자연수(1이상 10,000이하)가 주어지며 공백으로 구분한다.
단, K <= M

문제 풀이

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

data.sort()

# 가장 큰 수
top1 = data[n-1]
# 두 번째로 큰 수
top2 = data[n-2]

result = 0

while True:
    # 첫 번째 입력조건
    # n, m, k의 범위에 맞지 않는 숫자면 반복문 탈출
    if n not in range(2, 1000) or m not in range(1, 10000) or k not in range(1, 10000):
        print("Please enter a valid input")
        break

    # 두 번째 입력조건
    # K는 항상 M보다 작거나 같아야 함
    if k > m:
        print("Please enter a valid input")
        break

    for i in range(k): # 가장 큰 수 k번 더하기
        if m == 0 : # m이 줄어들다가 0이 되면 반복문 탈출
            break

        result += top1 # 가장 큰 수를 한 번 더하기
        m -= 1

    if m == 0: # m이 0이면 반복문 탈출
        break
    result += top2 # 두 번째로 큰 수를 한 번 더하기
    m -= 1

print(result)