알고리즘-그리디-만들 수 없는 금액

알고리즘-그리디-만들 수 없는 금액

 

문제 : N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 수하시오.

  N은 1 ~ 1000

  첫째줄에는 동전의 개수가 주어진다 ex)5

  둘째줄에는 동전의 금액이 주어진다. ex) 1 2 5 6 7

 

 

해결방안

 

1. N은 1~1000 이니 O(N3)

2. 금액 중 최솟값을 구해야한다 그리디 생각

3. 처음에 만들고자 하는 금액을 1원이라 생각하면 코인에는 무조건 1원이있어야한다.

target(만들고자하는금액) == coin(동전의 금액)

코인이 1원보다 크면안된다.

taget < coin 은 break

4. 다음 target은 기존 target값 + 첫번째 코인이여야한다. 처음에 1원을 만들수 있다면 다음 coin은 1원 혹은 2원이여야한다. 이 경우 taget < coin 이 될경우 만들 수 없다.

쭉 진행해보면    기존 타켓 + 전 코인  < 현재코인값   일 경우 기존타켓 + 전코인은 만들 수 없는 숫자이다.

 

쉽게말해 기존타켓은 이미 달성했음으로 논외로 치며  거기에 전 코인의값을 더했을 경우가 만들 수 있는 최대의 양의정수 값인데 해당 수가 현재코인의 값보다 작을 경우에는 다 더해도 현재 코인의 값 미만의 수를 만들 수 없다.

 

 

 

코드

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int N  = Integer.parseInt(bf.readLine());
    ArrayList<Integer> coin = new ArrayList<>();

    StringTokenizer st = new StringTokenizer(bf.readLine());

    for ( int i=0 ; i<N; i++) {
        coin.add(Integer.parseInt(st.nextToken()));
    }
    Collections.sort(coin);

    int target =1;
    for ( int i=0 ; i<coin.size(); i++) {
        if (target < coin.get(i)) {
            break;
        }
        else {
            target += coin.get(i);
        }
    }