greedy1 [백준] 11047 - 동전 0 (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 문제 풀이: 이 문제가 DP가 아니고 Greedy 문제라는 것을 알 수 있는게 문제에서 보면 주어지는 코인이 서로 배수 관계를 가지고 있으며 정렬되어 주어진다는걸 알 수 있다. 사실 배수관계만 유지되면 정렬은 우리가 해주어도 된다. 배수관계가 중요한 포인트인 이유는 배수관계를 유지함으로써 local optimal solution을 구하.. 2021. 3. 26. 이전 1 다음 반응형