[백준] 11047 - 동전0(그리디/python)

동전 0 

시간 제한/메모리 제한/제출/정답/맞힌 사람/정답 비율

1 초

256 MB

129352

68594

52608

52.158%

문제

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

---

풀이코드

# 동전개수, 목표금액
N, K = map(int, input().split())

# 동전 종류 리스트
coins = []
for _ in range(N):
    coins.append(int(input()))

# 결과값
count = 0

#큰수 동전부터 비교
coins.sort(reverse=True)
for c in coins:
    #나누어진 횟수
    count += K // c
    #큰수로 나누고 남은 금액
    K %= c
    #동전을 모두 확인하기 전에 목표금액 달성
    if K == 0:
        break

#결과값 출력
print(count)

 

큰 수부터 확인해야 최적의 해가 나올 수 있는 그리디 알고리즘 문제

나동빈님의 이코테 책에서 풀었던 동전문제와 비슷한것 같다.