점점 강해지고 있습니다.
[Java] 백준 11047번: 동전 0
풀이 방법
간단한 그리디 알고리즘 문제이다.
거꾸로 생각해서 가장 큰 동전부터 사용해서 0원 만들기를 하면 쉽게 풀 수 있다.
예제 1번은 4200원이니 4200원보다는 적지만 그 중에 가장 큰 액수부터 순차적으로 뺄셈해서 0원을 만들고, 그 때까지 사용한 동전의 개수를 세면 된다.
풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_11047_동전0 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] coins = new int[N];
for (int i = 0; i < N; i++) {
coins[i] = Integer.parseInt(br.readLine());
}
int coinCnt = 0;
int i= N-1;
while(K > 0) {
if(K < coins[i]) {
i--;
}
else {
K -= coins[i];
coinCnt++;
}
}
System.out.println(coinCnt);
}
}
Thank You For Reading
SeungJun Jeon