[백준] 1, 2, 3 더하기 4 (★) (15989번 JAVA)

[백준]  1, 2, 3 더하기 4 (!) (15989번 JAVA)

---

[접근 방법]

 

수식이 오름차순으로 정렬되어있어야 중복이 발생하지 않는다.

dp[ i ] 의 수를 구하기 위해선

dp[ i - 1 ] 의 방법 에 "+1 이 더하는 행위",

dp[ i - 2 ] 의 방법 에 "+2 이 더하는 행위",

dp[ i - 3 ] 의 방법 에 "+3 이 더하는 행위" 가 필요하다.

 

2차원 배열로서 이를 구현하고자 한다.

dp[ n ][ 수식의 마지막 수 ] 로 정의 한다.

 

예를 들어 n = 6 인 경우)

 

dp[ 3 ][ 1 ] = 1 // (1+1+1)

dp[ 3 ][ 2 ] = 1 // (1+2)

dp[ 3 ][ 3 ] = 1 // (3)

 

dp[ 4 ][ 1 ] = 1 // (1+1+1+1)

dp[ 4 ][ 2 ] = 2 // (1+1+2), (2+2)

dp[ 4 ][ 3 ] = 1 // (1+3)

 

dp[ 5 ][ 1 ] = 1 // (1+1+1+1+1)

dp[ 5 ][ 2 ] = 2 // (1+1+1+2), (1+2+2)

dp[ 5 ][ 3 ] = 2 // (1+1+3), (2+3)

 

이때 dp[6]은 

dp[ 6 ][ 1 ] = 1

(1+1+1+1+1 +1 ) // "(1+1+1+1+1)" 의 경우에 +1 을 하는 경우

 

dp[ 6 ][ 2 ] = 2

(1+1+1+1 +2 ) // "(1+1+1+1)" 의 경우에 +2 을 하는 경우

(2+2 +2 ) // "(2+2)" 의 경우에 +2 을 하는 경우

 

dp[ 6 ][ 3 ] = 3

(1+1+1 +3 ) // "(1+1+1)" 의 경우에 +3 을 하는 경우

(1+2 +3 ) // "(1+2)" 의 경우에 +3 을 하는 경우

(3 +3 ) // "(3)" 의 경우에 +3 을 하는 경우

 

따라서, 6을 만드는 경우의 수는 6가지 이다.

 

점화식은,

 

dp[ n ][ 1 ] = dp[ n-1 ][1]

dp[ n ][ 2 ] = dp[ n-2 ][1] + dp[ n-2 ][2]

dp[ n ][ 3 ] = dp[ n-3 ][1] + dp[ n-3 ][2] + dp[ n-3 ][3]

(단, n >= 4 인 경우)

 

로 나타낼 수 있다.

 

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        
        // 수식의 마지막 수 1 ~ 3
        long[][] dp = new long[10_001][4];
        dp[1][1] = 1; // 1
        dp[2][1] = 1; // 1+1
        dp[2][2] = 1; // 2
        dp[3][1] = 1; // 1+1+1
        dp[3][2] = 1; // 1+2
        dp[3][3] = 1; // 3
        
        /*
        모든 수식은 오름차순으로 정렬 되어있다고 가정
        */
        for(int i=4; i<=10_000; i++){

            /*
            수식의 마지막 수 <= 뒤에 추가될 수 있는 수 
            */

            dp[i][1] = dp[i - 1][1];
            dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
            dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
        }

        for(int i=0; i<T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n][1] + dp[n][2] + dp[n][3] + "\n");
        }

        bw.flush();
        bw.close();
    }
}