Greedy09동전0(11047)

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

풀이

• 이는 가장 큰 수부터 나누어 남은 몫을 더하면 된다
• 나머지는 K에 초기화 한 후 계속 나뉘는 대상이 되도록 한다.
• 나누는 수가 나누어 지는 수보다 크다면 몫은 0이다
• 그럼 for문만 돌려서 확인 가능하다

코드

import sys
sys.stdin = open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()

N, K = map(int,input().split())
arr = [int(input()) for _ in range(N)]
cnt = 0
# 이는 가장 큰 수부터 나누어 남은 몫을 더하면 된다 !!
# 나누는 수가 나누어 지는 수보다 크다면 몫은 0이겠지.
# 그럼 for문만 돌려서 확인 가능하다
for i in reversed(arr):
    cnt += K // i
    K = K % i
    if K == 0:
        break
print(cnt)

배운 것

동전을 더할 때 몫과 나머지를 이용하면 빠르게 게산 가능하겠구나.
'나누어 떨어지는 수'의 활용

코멘트