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

 

15989번: 1, 2, 3 더하기 4

 

 

사실 이 문제를 접하기 이전에 동전1 문제를 접했기 때문에 같은 논리를 적용하여 금방 해결할 수 있었다. 전체 코드는 맨 아래에...

 

[백준] 2293번 - 동전1

 

 

 

 

 

문제를 해결한 후 다른 사람들은 이 문제를 어떻게 해결했는지 궁금하여 구글링 해보았는데, 경우의 수 중에서 오름차순인 경우만 카운팅하는 방식을 사용하는 것을 보고 해당 방법도 적용해서 문제를 해결해 보았다.

 

오름차순을 이용하는 방법은 다음과 같다.

 

n = 4인 경우를 예시로 들어보자.

 

dp[a][b]에 들어가는 값은 더한 값이 a인 경우에서 숫자 b로 끝나는 경우(여기서 b는 1, 2, 3 세 가지중 1가지) 일 때,

 

문제에서 합을 이루고 있는 수의 순서가 다른 것은 같은 것으로 본다고 하였다. 즉 1 + 1 + 2 와 1 + 2 + 1 그리고 2 + 1 + 1 세 경우를 1가지 경우라고 생각한다는 의미이다.

 

합이 같으면서 순서만 다른 중복의 경우를 제외하기 위해서는 위 3가지 경우의 수 중에서 하나의 경우만 카운팅 해야 하는데, 조합이 오름차순인 경우만 카운팅 하면 중복을 줄일 수 있다. 위의 경우에서는 1 + 1 + 2 가 그 경우이다. 

 

추가로 n-1, n-2, n-3 세 가지 경우에 대해서 앞선 논리를 적용하여 합이 n인 경우의 수를 구하면 다음과 같다.

 

dp[n][1] = dp[n-1][1]; // 합이 n이고 1로 끝나는 경우의 수 중에 오름차순인 경우이므로 합이 n-1이고 1로 끝나는 경우에 1을 더하는 것만 가능하다.

dp[n][2] = dp[n-2][1] + dp[n-2][2]; // 합이 n이고 2로 끝나는 경우의 수 중에 오름차순인 경우이므로 합이 n-2이고 1로 끝나는 경우와 합이 n-2이고 2로 끝나는 경우에 2를 더하는 것이 가능하다. 

dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][3]; // 뒤에 붙는 3은 1, 2, 3 중 최대이므로 합이 n-3인 모든 경우의 수 뒤에 3을 더하는 것이 가능하다. 

 

합이 n인 경우의 수 = dp[n][1] + dp[n][2] + dp[n][3];

이다.

 

 

import java.io.*;

public class Main {
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int[][] dp = new int[10001][4];
        
        int T = Integer.parseInt(br.readLine());
        
        // 합이 3이하인 경우는 사전에 초기값 1을 넣어준다.
        dp[1][1] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
        
        // 주어지는 정수 n의 최댓값인 10000까지 경우의 수를 미리 저장해두고
        // 주어지는 n값에 대한 dp 를 출력한다.
        for (int j=4; j<=10000; j++) {
            dp[j][1] = dp[j-1][1];
            dp[j][2] = dp[j-2][1] + dp[j-2][2];
            dp[j][3] = dp[j-3][1] + dp[j-3][2] + dp[j-3][3];
        }
        
        for (int i=0; i<T; i++) {
            
            int n = Integer.parseInt(br.readLine());
            
            sb.append(dp[n][1] + dp[n][2] + dp[n][3] + "\n");
        }
        
        System.out.println(sb);
        
        br.close();
    }
}

 

 

 

 

동전1 문제와 같은 논리로 해결한 코드

 

Top-Down

import java.io.*;

public class Main {
    
    static Integer[][] dp;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        for (int i=0; i<T; i++) {
            
            int n = Integer.parseInt(br.readLine());
            
            dp = new Integer[4][n+1];
            
            for (int j=0; j<=n; j++) dp[0][j] = 0;
            
            dp[0][0] = 1;
            
            sb.append(recur(3, n) + "\n");
        }
        
        System.out.println(sb);
        
        br.close();
    }
    
    static int recur (int n, int v) {
        
        if (dp[n][v] == null) {
            
            if (n > v) dp[n][v] = recur(n-1, v);
            else dp[n][v] = recur(n-1, v) + recur(n, v-n);
        }
        
        return dp[n][v];
    }
}

문제에서 메모리 제한 조건은 512MB으로 넉넉하지만 내 PC에 설치된 이클립스는 스택영역에 할당된 메모리 크기가 512MB보다 적어서 StackOverFlow가 발생한다(위 풀이에서 초기에 recur(3, 10000) 을 실행하여 최초 생성한 dp를 여러 테스트 케이스에 공유하여도 마찬가지로 메모리가 부족하다).

 

이는 n이 최대값일 때 (n=10000) 재귀가 너무 깊어져서 필요로 하는 메모리 공간이 Bottom-Up 방식에 비해 많이 크기 때문에 발생하였다고 생각한다.

 

 

Bottom-Up

import java.io.*;

public class Main {
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        int[][] dp = new int[4][10001];
            
        dp[0][0] = 1;

        for (int j=1; j<4; j++) {
            for (int k=0; k<=10000; k++) {
                if (j > k) dp[j][k] = dp[j-1][k];
                else dp[j][k] = dp[j][k-j] + dp[j-1][k];
            }
        }
        
        for (int i=0; i<T; i++) {
            
            int n = Integer.parseInt(br.readLine());
            
            sb.append(dp[3][n] + "\n");
        }
        
        System.out.println(sb);
        
        br.close();
    }
}