백준 11047. 동전 0 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	
	public static void main(String[] args) throws 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 index = N - 1;
		int[] Money = new int[N];
		
		for(int i = 0 ; i < Money.length; i++) {
			
			Money[i] = Integer.parseInt(br.readLine());
	
		}
		
		int cnt = 0;
		
		while(K > 0) {
			
			if(K < Money[index]) {
				
				index--;
				
			}
			else if(K >= Money[index]) {
				
				cnt += (K / Money[index]);
				
				K %= Money[index];
				
			}
			
		}
		System.out.println(cnt);
	}
}

○ 문제 요약

입력받은 K의 값을 입력받은 N의 값으로 나눴을 때 나올 수 있는 최솟값을 출력해라. 

○ 문제 풀이

알고리즘 분류는 그리디 알고리즘이고 이전에 풀은 ATM 문제와 같은 알고리즘이다.

 

특별히 어려운 부분은 없지만 while문은 보고 지나가고 싶다.

while문의 조건을 보면 K가 0보다 클 때까지 수행하고

만약 Money[index]의 값이 K보다 크다면 작거나 같아질 때까지 index-- 한다.

 

else if 조건을 성립하면 K / Money[index]한 값을 cnt += (K/Money[index]) 해주고

K % Money[index] 값을 다시 K에 넣어줘 이 과정을 반복해서 수행하도록 한다.

 

그러면 K가 0보다 작아졌을 때,

while문을 탈출하고 cnt를 출력해주면 최솟값을 출력할 수 있다.   

○ 결과