이코테 - 만들 수 없는 금액 with JAVA

 

 

 

 

문제

N개의 동전으로 만들 수없는 양의 정수 중 최솟값을 구하라

 

 

 

로직

예를 들어, [1, 1, 2, 3, 9] 원이 있다고 가정하자.

1. 1원을 가지고는 1원까지 만들 수 있다.

2. 1원을 가지고는 2원까지 만들 수 있다.

3. 2원을 가지고는 4원까지 만들 수 있다.

4. 3원을 가지고는 7원까지 만들 수 있다.

5. 9원을 가지고는 16원까지 만들 수 있다.

 

증명

1원 - 1

2원 - 1, 1

3원 - 1, 2

4원 - 1, 1, 2

5원 - 3, 2

6원 - 3, 2, 1

 

즉, 결론적으로 a원을 가지고 있다면 기존에 만들 수 있는 금액 m원에 더해 a+m원까지 만들 수 있다.

 

 

 

 

코드 

import java.util.*;

public class Q4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String n = scanner.nextLine();
        String value = scanner.nextLine();
        String[] values = value.split(" ");
        

        List<Integer> result = new ArrayList<>();
        for(String now : values){
            result.add(Integer.valueOf(now));
        }
        Collections.sort(result);

        int target = 1;
        for(int i : result){
            // 새롭게 꺼낸 동전이 현재까지 만들 수 있는 금액보다 작아야 가능
            if(i > target){
                break;
            }
            target += i;
        }
        
    }
}