알고리즘 문제 풀이/BOJ 실버
[백준] 11047 - 동전 0
natonato
2022. 1. 16. 15:43
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
0. 최소한의 갯수로 목표 금액을 맞추는 문제
1. 모든 고액권은 소액권의 n배수로 떨어지므로, 항상 가장 큰 액수부터 선택하는게 유리하다
- 그리디 알고리즘
2. 목표 금액을 초과하지 않는 선에서, 가능한 많은 금액을 고액권부터 채워나간다
3. 목표 금액이 완성되면, 최종 갯수를 출력
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = pint(st.nextToken());
int k = pint(st.nextToken());
int[]money = new int[n];
for (int i = 0; i < n; i++) {
money[i]=pint(br.readLine());
}
int cnt=0, idx=n-1;
while(k!=0) {
cnt+=k/money[idx];
k%=money[idx--];
}
System.out.println(cnt);
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
