[백준] #11047 동전 0 (python)

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

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

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

예제 출력1

6

 

예제 입력2

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

예제 출력2

12

---

# Code

n, k = map(int, input().split())
coin = [int(input()) for _ in range(n)]
cnt = 0

coin.sort(reverse=True)

for i in range(n):
    if coin[i] > k:
        continue
    else:
        cnt += k//coin[i]
        k = k%coin[i]

print(cnt)

# Comment

음... 꽤 고민했는데 간단한 문제였다... 머쓱..... 졸려서 머리가 잘 안굴러간 거라고 믿는다.

 

나는 일단 coin들을 입력받아서 큰 것부터 내림차순 정렬해주었다. 그리고 while문 안에서 만약에 k보다 큰 coin이 나오면 그냥 continue를 통해 넘어가도록 했고, 그렇지 않으면 k를 해당 coin으로 나눈 몫을 count에 더해주고 k값은 k를 coin으로 나눈 나머지로 바뀌도록 구현했다.

앞으로 엔터키를 통해서 여러 입력값을 list에 받을 필요가 있을 때 [int(input()) for _ in range(n)] 을 많이 사용해 볼 예정이다. 아주 간편하고 좋은 것 같다. ㅎㅎ