백준: 11047 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

1. 정렬되있음->뒤에서부터 탐욕적으로 탐색

2. K보다 작거나 같은 최대값 선택

3.반복적으로 빼고, 카운트++

4.K==0이면 브레이크, 답 출력

5.현재 선택된값이 K보다 커지면 다시 탐욕적 탐색 , 3번으로가서 반복

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

public class Main_11047_유동훈 {
	
	static int N;
	static int K;
	static int[] arr;
	static int count;
	
	static int search()
	{
		for(int i=0;i<N-1;++i)
        {
        	if(arr[i]<=K)
        	{
        		if(arr[i+1]<=K)
        			continue;
        		else
        			return i;
        	}
        	//else
        		//return 0;	
        }
		return 0;
	}
	public static void main(String[] args) throws IOException 
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N= Integer.parseInt(st.nextToken());
        K= Integer.parseInt(st.nextToken());
        
        arr=new int[N];
        for(int i=0;i<N;++i)
        {
        	arr[i]=Integer.parseInt(br.readLine());
        }
        
        //int current=arr[search()];
        int index=0;
        for(int i=N-1;i>=0;--i)
        {
    		if(arr[i]<=K)
    		{
    			index=i;
    			break;
    		}
        }
        while(true)
        {
        	if(K==0) break;
        	
        	
        	if(arr[index]>K) 
        	{
        		for(int i=N-1;i>=0;--i)
                {
            		if(arr[i]<=K)
            		{
            			index=i;
            			break;
            		}
                }
        	}
        	
        	K=K-arr[index];
        	count++;
        }
        
        System.out.println(count);
        
        
        
        
        
	}
}