동전0

자바(Java) 알고리즘 문제풀이 동전0 [백준 / 그리디]

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 풀이 코드 전형적인 그리디 문제로 가능한 큰 동전으로 연산하며 가능한 최소한의 동전 갯수를 구하는 문제이다. 그리디로 접근 시 주의해야할 점이 있는데, 문제 설명을 보면 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 라고 명시 되어있는 것을 볼 수 있다. 쉽게 말하자면 각 동전의 가치는 서로 배수관계에 있다는 뜻이며 이 입력이 보장되기 때문에 그리디로..