[BOJ] 11047: 동전 0

난이도: 실버4

문제

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

 

---

풀이 기록

1. 변수 네이밍

N; 코인 종류 수, K: 원하는 금액

coin (list) : 코인 종류를 저장할 리스트

cnt: 필요한 동전의 개수

 

2. 알고리즘

 

먼저 N의 크기만큼 coin.append 를 통해 숫자를 차례차례 입력받는다.

 

조건에 의하면, 동전은 직전 동전의 배수이다. 그렇기에 제일 큰 금액의 동전부터 계산해보자.

 

예시 입력이 

4 4200

100

500

1000

5000

이라고 하자.

 

1. 5000으로 나누면 K 가 아무 변화 없이 나머지로 남는 것을 확인할 수 있다.

(K % coin[-1] == K)

 

2. 다음 단계인 1000으로 나눌 때는, K % coin[-2] != K 이다.

이럴 경우, K // coin[-2] 의 개수만큼 동전이 필요하다.

 

3. 그 다음, 500으로 나눌 때는, 4200-4000 으로 남은 금액이 200원이기 때문에

K % coin[-3] == K . 즉, 나머지로 그대로 남아버리는 경우가 된다.

 

1번 과정과 3번 과정의 조건이 동일하다.

그렇기에 if문을 통해 조건을 세워준다.

if K % coin[-n] != K:
    cnt+= K // coin[-n]
    K %= coin[-n]

이와 같이 해결할 수 있다.