백준 11047번 - 동전0

출처: 11047번: 동전 0 (acmicpc.net)

11047번: 동전 0

---

동전 0 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

256 MB

46502

24733

19545

52.869%

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

---

[ 문제 풀이 ]

 

문제에서 n, k = 동전의 종류, 목표 금액이 주어집니다.

 

이문제는 하나씩 다 따져가면서 상황 상황을 코딩해야 하는 문제입니다.

예시에서 나온 4200원을 예시로 들겠습니다.

우선 여기서 입력 조건에서 넘겨짚어야 하는 부분은  (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)입니다.

이 조건에 의해 저희는 // 연산으로 쉽게 풀 수 있게 됩니다

우선 동전의 종류는 1 5 10 50 100 500 1000 5000 10000 50000입니다.

4200원은 1000원이 4번 들어갈 수 있지요.

이 표현을 4200 // 1000 = 4 이 되고, 위의 상황을 코딩한 게 되죠.

그럼 목표치 4200원을 4 * 1000 만큼 빼주면 200원이 됩니다.

또 200원은 100원 2번이 되는 상황

같은 원리로 200 // 100 = 2 가 되고, 2 * 200을 빼주면 0원이 되며 이 순간 상황이 종료되게 코딩하면 되는 겁니다.

 

코드 부분을 보겠습니다.

 

---

n, k = map(int, input().split())

coins = []
res = 0
cnt = 0

for i in range(n):
    i = int(input())
    coins.append(i)

coins.reverse()

for c in coins:
    if k // c == 0:
        continue
    else:
        cnt = k // c
        res += cnt
        k = k - (cnt * c)
        if k == 0:
            break
print(res)

 

---

후기

 

간단한 그리디의 첫걸음 문제