https://www.acmicpc.net/problem/11047
11047번: 동전 0첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)www.acmicpc.net
dp만풀다가 푸니깐 힐링된다.
k=돈
cnt=횟수
먼져, 동전의 가치를 리스트로 저장해준다.
그리고, 가장 큰 동전이 k보다 작을때까지 pop해준다.
그후, (k//가장큰 동전) 을 cnt에 추가해주고 (동전을 몇번사용했는가)
(k%가장큰동전)을 k로 선언한다. (동전을 최대한 쓰고 남은 돈)
이를 0이될때까지 반복한다.
(1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 라는 조건덕분에 그리디알고리즘이 성립된다.
만일 a[3]을 쓸수 있다면, 어떠한 경우에도 a[2]를 쓰는 것보다 효율적이다.
코드
n,k=map(int,input().split())money=[]for _ in range(n):
money.append(int(input()))cnt=0while k > 0: while money[-1] > k:
money.pop() a,k=divmod(k,money[-1]) cnt+=a print(cnt)