목록그리디 알고리즘 (1)

철갑이의 이모저모

[백준] 11047번(동전 0) with Python

문제 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 풀이 동전의 갯수가 최솟값을 가져야 하기 때문에 큰 수 부터 나눠준다. 동전의 가치가 오름차순으로 입력이 되기 때문에 coin[::-1](리스트 역으로 출력) 사용, pop() 으로 작성해도 된다. 1. k원을 동전의 가치로 나눠주고(몫만 필요하기 때문에 // 사용) 2. k원에서 (1에서 나온 몫 * 동전의 가치)를 빼준 후 3. 코인 개수..
알고리즘 2020. 11. 24. 23:06
이전 Prev 1 Next 다음