티스토리 뷰
728x90
반응형
문제
백준 11047, 탐욕적 기법 ( Greedy Algorithm )
문제
준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
접근&풀이
A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수
이것이 조건으로 주어지기 때문에
가장 큰 ~ , 가장 빠른 ~ 의 그리디 알고리즘의 성질을 이용하여 쉽게 해결 가능.
마지막 동전의 가치가 가장 크기 때문에, 큰 것부터 비교해가며 K 원을 만들면 된다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | package BaekJoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class B11047 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().split("\\s+"); int N = Integer.parseInt(line[0]), K = Integer.parseInt(line[1]); int[] coin = new int[N]; for (int i=0; i<N; i++) { coin[i] = Integer.parseInt(br.readLine()); } int count = 0; for (int i=N-1; i>=0; i--) { if (coin[i] > K) { continue; } else { count += K/coin[i]; K %= coin[i]; } } System.out.println(count); } } | cs |
반응형
'프로그래밍 > Algorithm' 카테고리의 다른 글
[Algorithm] 백준 2805 (0) | 2019.02.17 |
---|---|
[Algorithm] 개요 (0) | 2018.12.11 |
공지사항
최근에 올라온 글