(Baekjoon) GreedyAlgorithm - (2) 동전 0

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

11047번: 동전 0

 

6 4103

----------

1

2

3

100

500

1000

----------

 

이런식으로 되어있을때 다음과 같이 생각해보면 된다.

(단 오름차순으로 정렬되어있을때의 코드이다.)

 

4103 보다작은수 1000선택
3103 보다 작은수 1000선택
2103 보다 작은수 1000선택
1103 보다 작은수 1000선택
103 보다 작은수 100 선택
3 보다 작은수 1선택
2 보다 작은수 1선택
1 보다 작은수 1선택

(K == 0) >> 종료 // K는 제시한수

 

해당 K보다 작은수를 K에서 빼고 count++ 증가로해주면된다.

 

package GreedyAlgorithm;

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

public class _11047 {

    public static void main(String[] args){
        try {
            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 coin[] = new int[N];
            for (int i = 0; i < N; i++) 
                coin[i] = Integer.parseInt(br.readLine());
            int count=0;
            while(K != 0){
                    for (int i = coin.length - 1; i >= 0; i--) {
                        if(coin[i] <= K){
                            K -= coin[i];
                            break;
                        }
                    }
                    count++;

            }
            System.out.println(count);
            
            
        } catch (IOException e) {
            e.printStackTrace();
        }
        

    
    }
}

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study