[Python] 백준 11047번 "동전 0" (그리디)

문제

11047번: 동전 0

입력

• 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
• 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다.
• (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

• 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

문제 풀이

• 현재까지 계산된 결과와 연산을 수행 할 변수 만들기
• 동전의 금액을 배열에 저장해 내림차순으로 정렬(높은 금액의 액수부터 계산)
• 동전을 하나씩 꺼내보면서 현재 값과 동전의 액수를 나눈 결과가 0보다 큰 경우 
• 동전으로 연산을 수행할 수 있다는 뜻이므로 동전을 세고있는 res에 그 값을 넣어 동전 수 카운트
• 그 후 현재까지 계산된 값을 저장하는 변수에  동전액수 * 동전의 개수를 더해준다
• 그 후 목표 값을 동전의 액수로 나눈 값의 나머지가 남은 값이므로 이 값으로 다음 연산 수행
• 현재 값이 목표 값보다 작은 경우 위의 모든 과정 반복
• 그 후 동전의 개수 출력

코드

n,k = map(int,input().split())
number = k
data = []
res = 0
cnt = 0
cur = 0
# 입력받기
for i in range(n):
    num = int(input())
    data.append(num)
    data.sort(reverse=True)

while cur < k:
    for sum in data:
        if number // sum > 0:
            res += number // sum
            # cur은 현재까지 더해진 값
            # 몫을 더한 횟수에 더하고, 나머지 다시 연산
            cur += (sum * (number // sum))
            number %= sum

print(res)