[Algorithm] 백준 11047 동전 0 with Python

문제

준규가 가지고 있는 동전은 총 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 

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1 

6

---

내가 짠 코드

num, price = map(int, input().split())
coins = [int(input()) for _ in range(num)]  #동전들을 리스트로 저장
coins.reverse()  #내림차순으로 변환(가장 먼저 검사해야 할 값을 앞으로 보내기)

cnt= 0 #사용되는 동전의 개수
for coin in coins:
        if price / coin < 1:  #동전이 목표 금액보다 클 때는 스킵
                continue
        if price / coin == 1:  #동전이 목표 금액과 같다면 카운트 후 break
                cnt += 1
                break
        else:  #동전이 목표 금액보다 작다면 
                cnt += price // coin  #금액에서 동전을 나눈 몫을 카운트에 더하기
                price = price % coin  #금액에서 동전을 나눈 나머지를 다시 금액으로 업데이트
print(cnt)

차근차근 경우의 수들을 생각을 하며 동전이 목표 금액보다 클 때, 같을 때, 적을 때를 각각 나눠서 코드를 짜보았다.

정답은 맞았으나 다른 코드들을 살펴보니 훨씬 짧고 효율적인 방법이 존재했다.

 

N, K = map(int, input().split()) # 정수 데이터 타입으로 변환하여 숫자를 N,K에 각각 저장

coins = [int(input())  for _ in range(N)] # 동전의 종류를 coins에 저장
coins.reverse() #내림차순으로 변환(가장 먼저 검사해야 할 값을 앞으로 보내기)
ans = 0
for coin in coins:
  ans +=  K // coin # K를 내림차순으로 정렬된 coin으로 나누어주면 몫을 ans에 저장
  K %= coin # coin으로 나눈 나머지를 K에 저장

print(ans)

돟전이 금액보다 크거나 같거나 작거나 상관없이 그냥 몫과 나머지만 생각하면 되는 것이었다.

동전이 금액보다 크다면 어짜피 나눈 몫은 0이고 나머지는 금액 그대로가 되기 된다. 

동전과 금액이 같을 때도 마찬가지로 몫은 1이고 나머지는 0이니 굳이 케이스를 나눌 필요가 없었다. 

 

조금더 깊게, 꼼꼼하게 생각하는 습관을 길러야 겠다.

 

 

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0