BOJ 11047 동전 0

동전 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력

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

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

예제 출력

6

12

풀이

주어진 동전의 가치를 기준으로 내림차순으로 정렬한 후
하나씩 탐색하면서 동전의 가치가 가치의 합(K)보다 작거나 같은 경우
가치의 합(K)를 동전의 가치로 나누어 사용하는 동전의 개수에 더해주어 해결했다.
또한 가치의 합(K)를 사용한 동전의 가치로 나눈 나머지를 가치의 합(K)에 대입해
남은 가치의 합을 계산하는 방식으로 해결할 수 있었다.

조금 특별하게 푼 점이 있다면 데이터를 정렬하지 않고,
문제에서 오름차순으로 데이터가 주어진다고 알려주었기 때문에
리스트의 맨 앞에 새로운 데이터를 삽입해 내림차순으로 정렬되게 하였다.
리스트를 추가로 정렬하지 않았기 때문에 어느정도 효율성이 좋아졌을 것 같다.

코드 구현부

풀이에서 작성하였듯이 insert함수를 사용해 0번째 인덱스에 새로운 값을 저장했다.

N, K = map(int, input().split())
coins, count = [], 0

for _ in range(N):
    coins.insert(0, int(input()))

for coin in coins:
    if coin <= K:
        count += (K // coin)
        K %= coin

print(count)

결과

정답률 59%의 문제로 어렵지 않게 해결할 수 있었다.

✅ 코드는 [여기]에서 확인할 수 있다.