백준 알고리즘 - 11047 - 동전 0

문제

준규가 가지고 있는 동전은 총 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 받기
2. N줄 동전 입력 받기 (coin)
3. 동전 개수의 최솟값 구하기
   1. 4200 / 1000 = 4
      4200 - 1000 × 4 = 200
   2. 200 / 500 = 0
      200 - 500 × 0 = 200
   3. 200 / 100 = 2
      200 - 100 × 2 = 0

 

최대 단위의 동전 개수 저장 (num)

최대 단위의 동전 만큼 빼주기 = 거스름돈 (change)

---

코드

N, K = map(int, input().split())
coin = [0]*N 
answer = 0

for i in range(N):
    coin[i] = int(input())

for i in range(1, N+1):
    answer += K // coin[-i] # 동전 개수
    K = K % coin[-i] # 거스름돈

print(answer)

---

풀이

Greedy 문제이다. 처음에 거스름돈을 어디에 저장할지 많이 헤맸다.

for i in range(N):
    num = K // coin[-i]
    answer += num
    change = K - coin[-i] * num

이런 식으로 몫(num)을 따로 구하고 그것을 출력할 answer에 또 저장하는 불필요한 작업이 있었다.

 

거스름돈(change)을 따로 저장하게 되면 처음에 K를 coin으로 나누는 작업이 첫번째 줄에서 이루어져야 하는데, 그러면 for문의 첫번째에 써야했고 이것은 두번째 반복할 때에도 다시 K를 coin으로 나누게 되는 작업이 이루어져서 잘못된 접근 방식이었다.

 

거스름돈(change)를 만들 필요 없이 K를 coin으로 나누어 준 것을 다시 K에 넣어주면 따로 change를 만들 필요도 없으며 위의 문제를 해결할 수 있다.

 

또한 몫(num)을 만들어 줄 필요 없이 몫 연산(//)과 나머지 연산(%)을 이용하면 된다.

 

몫과 거스름돈 같은 변수를 또 생성해서 이용하는 방법말고 이미 존재하는 변수를 중복으로? 다시 활용하는 것이 정말 중요하다고 생각한다!

---

당연히 알아야 하는 것

1. 리스트의 맨 마지막 인덱스는 -1 이다.

 

2. 한 줄씩 입력 받기

for i in range(N):
    coin[i] = int(input())