[백준] 2294번 : 동전2

문제

 

 

접근 방식

이전 동전 문제처럼 k원을 만드는 모든 경우의 수를 구하는 것이 아니라

가장 적은 수의 동전을 사용해 k원을 만들 수 있는 경우를 구해야 한다.

 

5원, 1원, 12원 총 3개의 동전으로 15원을 만들어야 할 때

5원으로 15원을 만들 수 있는 경우를 먼저 생각해 보자

1원을 만드는 경우 : X
2원을 만드는 경우 : X
3원을 만드는 경우 : X
4원을 만드는 경우 : X
5원을 만드는 경우 : 1
6원을 만드는 경우 : X
7원을 만드는 경우 : X
8원을 만드는 경우 : X
9원을 만드는 경우 : X
10원을 만드는 경우 : 2
11원을 만드는 경우 : X
12원을 만드는 경우 : X
13원을 만드는 경우 : X
14원을 만드는 경우 : X
15원을 만드는 경우 : 3

 

위와 같이 5원 동전은 5원 이상의 값부터 사용할 수 있으니 자기 자신부터 1로 시작할 것이다.

 

N원을 만드는 경우는 (N-5)원에 5원 동전을 하나 더 사용한 것이니 DP[N-5] + 1이 되고

10원을 만드는 경우는 DP[5] + 1인 2, 15원을 만드는 경우는 DP[10] + 1인 3이 되는 것이다.

 

나머지 금액들은 5원만으로는 만들 수 없는 금액이니 DP[6-5]나 DP[7-5]처럼 0인 경우는 건너뛰면 된다.

 

이제 1원까지 사용한 경우를 계산해 보겠다.

1원을 만드는 경우 : 1
2원을 만드는 경우 : 2
3원을 만드는 경우 : 3
4원을 만드는 경우 : 4
5원을 만드는 경우 : 1 < 5
6원을 만드는 경우 : 2
7원을 만드는 경우 : 3
8원을 만드는 경우 : 4
9원을 만드는 경우 : 5
10원을 만드는 경우 : 2
11원을 만드는 경우 : 3
12원을 만드는 경우 : 4
13원을 만드는 경우 : 5
14원을 만드는 경우 : 6
15원을 만드는 경우 : 3

 

1 ~ 4원은 당연히 값만큼의 동전수가 사용될 것이고 DP[5]를 채우는 경우를 살펴보면

기존에 5원짜리 동전 하나만 사용하는 경우가 1원짜리 동전 5개를 사용하는 것보다 효율적이니

둘 중 더 작은 값으로 채워주면 된다.

 

12원 동전까지 사용하는 경우도 살펴보자

1원을 만드는 경우 : 1
2원을 만드는 경우 : 2
3원을 만드는 경우 : 3
4원을 만드는 경우 : 4
5원을 만드는 경우 : 1
6원을 만드는 경우 : 2
7원을 만드는 경우 : 3
8원을 만드는 경우 : 4
9원을 만드는 경우 : 5
10원을 만드는 경우 : 2
11원을 만드는 경우 : 3
12원을 만드는 경우 : 4 > 1
13원을 만드는 경우 : 2
14원을 만드는 경우 : 3
15원을 만드는 경우 : 3 < 4

 

12원 동전도 마찬가지로 12원부터 DP 테이블을 더 작은 값으로 갱신해 주면 된다.

 

사소한 걸 놓쳐서 여러 번 틀렸던 문제인데

DP 배열이 비어있는 경우에는 초기값인 0으로 설정되어 있기 때문에

항상 비교하면 0이 제일 작아 테이블이 정상적으로 채워지지 않는다.

 

배열을 생성하고 테이블을 채우기 전에 큰 값으로 초기화해주거나

테이블을 채우면서 0인 경우는 비교 없이 채우게 분기를 만들어 줘야 한다.

 

풀이

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[] dp = new int[100001];
        boolean[] isUsed = new boolean[100001];
        
        for (int i = 0; i < n; i++) {
            int coin = Integer.parseInt(br.readLine());
            
            if (isUsed[coin]) continue;
            isUsed[coin] = true;
            dp[coin] = 1;
            
            for (int j = coin + 1; j <= k; j++) {
                if (dp[j - coin] == 0) continue;
                if(dp[j] != 0) dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                else dp[j] = dp[j - coin] + 1;
            }
        }
        
        System.out.println(dp[k] != 0 ? dp[k] : -1);
    }
}