11047_동전0 (JAVA)

11047번: 동전 0

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] coin = new int[N];
		int maxN=0;
		for(int i=0; i<N; i++){
			coin[i] = sc.nextInt();
			if(coin[i]<=K) maxN = i;
		}
		
		int ans=0;
		while(maxN>=0){
			if(K/coin[maxN]!=0){ //몫이 0이 아니면 나눠떨어진다는 의미
				ans+=K/coin[maxN];
				K%=coin[maxN];
				
				if(K==0) break;
			}
			maxN--;
		}
		
		System.out.println(ans);
	}
	
}

 

[문제 풀이 생각 과정]

1. 입력받은 동전의 종류 중에서, K보다 큰 동전은 계산에 이용되지 않는다.

   제외시키고 생각하기 위해서 maxN을 구했다.

2. maxN부터 0 순으로 (동전종류의 내림차순으로) K를 나눠준다.

   만약 K/coin[i]!=0 이라면 즉, 몫이 0이 아니라면 나눠떨어진다는 의미이고,

   이를 내림차순으로 확인하고 있기 때문에- 필요한 동전 개수의 최솟값에 포함된다!

   ans+=K/coin[i]; (몫을 더해준다)

   K%=coin[i]로 계산해야 하는 K값을 수정해준다. 

 

   K/coin[i]==0이라면 즉, 몫이 0이라면 나눠떨어지지않기 때문에 제외시킨다.

  (i-1번째로 이동 후 다시 확인)

3. 확인하는 과정에서 K가 0이 된다면 확인이 끝났다는 의미! break로 종료한다