[백준] 2293번 - 동전1

2293번: 동전 1

 

 

 

백준의 다른 문제인 1, 2, 3 더하기 4 문제와 같은 논리를 적용하면 된다.

 

[백준] 15989번 - 1, 2, 3 더하기 4

 

문제 조건을 살펴보면 주어지는 n가지 종류의 동전을 사용하여 가치의 합이 k원이 되도록 하는 경우의 수를 구하는데, 각 동전은 원하는 만큼 사용할 수 있고 동전 구성이 같고 순서만 다른 경우의 수는 1가지 경우로 취급한다고 나온다.

 

점화식을 세우면 다음과 같다. (coin[i]는 i번째 동전의 가치)

 

i) i 번째 동전이 가치의 합 j 보다 큰 경우는 i - 1 번째 동전까지만 사용하여 j를 만드는 경우의 수가 그대로 dp[i][j]에 들어간다.

ii) i 번째 동전이 가치의 합 j 보다 같거나 작은 경우 (ㄱ) i번째 동전을 사용하지 않고 j를 만드는 경우 (ㄴ) i번째 동전을 사용하고 j를 만드는 경우를 구한 다음 (ㄱ) + (ㄴ) 을 dp[i][j]에 넣는다.

 

이때 (ㄴ)의 경우  j - (i번째 동전의 가치)를 만드는 경우의 수에 i번째 동전의 가치를 추가해 주는 것이므로 dp[i][j-coin[i]] 이다.

 

따라서 점화식을 세우면

 

if ( coin[i] > j ) dp[i][j] = dp[i-1][j];

else dp[i][j] = dp[i-1][j] + dp[i][j - coin[i]];

 

이다.

 

 

전체 코드

import java.io.*;

public class Main {
    
    static int[] coin;
    static Integer[][] dp;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] input = br.readLine().split(" ");
        
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        
        coin = new int[n+1];
        dp = new Integer[n+1][k+1];
        
        for (int i=0; i<k+1; i++) dp[0][i] = 0;
        dp[0][0] = 1;
        
        for (int i=1; i<n+1; i++) coin[i] = Integer.parseInt(br.readLine());
        
        System.out.println(countCases(n, k));
        
        br.close();
    }
    
    static int countCases (int ct, int v) {
        
        if (dp[ct][v] == null) {
            if (coin[ct] > v) dp[ct][v] = countCases(ct-1, v);
            else dp[ct][v] = countCases(ct-1, v) + countCases(ct, v-coin[ct]);
        }
        
        return dp[ct][v];
    }
}

 

 

 

그런데 순수한 문제의 조건 외에 출제자가 메모리 제한 조건을 의도적으로 조금밖에 주지 않은 것을 알 수 있다. 따라서 필요한 메모리를 더 줄이기 위한 방법을 고민해볼 필요가 있다(물론 위의 코드도 성공적으로 제출된다.);

 

앞선 해결법에서는 dp를 이중배열로 만들어 동전을 n번째까지 사용 하여 가치의 합이 j가 되게 하는 모든 경우를 메모제이션 하였다. 

 

다른 방법으로는 dp를 이중 배열이 아닌 그냥 배열로 두고도 해결할 수 있다. 

 

결국 최종적으로 필요한 데이터는 '모든 동전을 사용하여 가치의 합이 k가 되게 하는 모든 경우의 수' 이므로,

dp[k] 값에 이전 값들을 누적한다면 보다 적은 수의 동전을 사용하여 합이 k 가 되게 하는 경우를 별도로 저장하지 않아도 된다. 

 

 

전체 코드

import java.io.*;

public class Main {
    
    static int[] coin;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] input = br.readLine().split(" ");
        
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        
        coin = new int[n+1];
        int[] dp = new int[k+1];
        
        dp[0] = 1;
        
        for (int i=1; i<n+1; i++) coin[i] = Integer.parseInt(br.readLine());
        
        for (int i=1; i<n+1; i++) {
            for (int j=0; j<k+1; j++) {
                if (coin[i] <= j) dp[j] = dp[j] + dp[j-coin[i]]; 
            }
        }
        
        System.out.println(dp[k]);
        
        br.close();
    }
}