BOJ - 11047 ) 동전 0

---

 

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

11047번: 동전 0

---

동전이 무수히 많고, A(i) 번째는 A(i-1) 번째의 배수이므로

 

그리디가 성립한다.

---

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 answer =0;
       int Num[] = new int[N];
       for(int i=0;i<N;i++) {
    	   Num[i] = Integer.parseInt(br.readLine());
       }
       
       while(K!=0) {
    	    if(K-Num[N-1] >= 0) {
    		       K-=Num[N-1];
    		       answer++;
            } else {
    	    N--;	
            } 
       }
       System.out.println(answer);              
	}
}

---