[백준] 1, 2, 3 더하기 7 (15992번 JAVA)

[백준]  1, 2, 3 더하기 7 (15992번 JAVA)

---

[접근 방법]

 

2차원 배열로 dp를 선언해야 한다.

dp[n][m] = dp[수식의 합][수식의 수 개수] 로 정의한다.

        long[][] dp = new long[1_001][1_001];
        dp[1][1] = 1; // 1
        dp[2][1] = 1; // 2
        dp[2][2] = 1; // 1+1
        dp[3][1] = 1; // 3
        dp[3][2] = 2; // 1+2, 2+1
        dp[3][3] = 1; // 1+1+1

위와 같이 초기값을 정의한다.

 

n이 4인 경우를 예로 들겠다.

 

dp[4][1] = 0

4를 한개의 숫자로 구성할 수 없다.

 

dp[4][2] = 3

4를 2개의 숫자로 구성하는 경우는 (1 + 3) , (2 + 2), (3 + 1) 과 같다.

이 경우, dp[3][1] + dp[2][1] + dp[1][1]의 경우와 같다.

 

dp[4][3] = 3

4를 3개의 숫자로 구성하는 경우는 (1 + 1 + 2) , (1 + 2 + 1), (2 + 1 + 1) 과 같다.

이 경우, dp[3][2] + dp[2][2] + dp[1][2]의 경우와 같다.

 

dp[4][4] = 1

4를 4개의 숫자로 구성하는 경우는 (1 + 1 + 1 + 1) 과 같다.

이 경우, dp[3][3] + dp[2][3] + dp[1][3]의 경우와 같다.

 dp[2][3] 와 dp[1][3] 의 경우는 존재할 수 없기 때문에 0 이다.

 

따라서, 도출되는 점화식은

dp[n][m] = dp[n-1][m-1] + dp[n-2][m-1] + dp[n-3][m-1] (단 n>=4 , m>=1) 

이다.

---

[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));

        int T = Integer.parseInt(br.readLine());
        
        long[][] dp = new long[1_001][1_001];
        dp[1][1] = 1; // 1
        dp[2][1] = 1; // 2
        dp[2][2] = 1; // 1+1
        dp[3][1] = 1; // 3
        dp[3][2] = 2; // 1+2, 2+1
        dp[3][3] = 1; // 1+1+1

        for(int i=4; i<=1_000; i++){
            for(int j=1; j<=i; j++){
                dp[i][j] = (dp[i-1][j-1] + dp[i-2][j-1] + dp[i-3][j-1]) % 1_000_000_009;
            }
        }

        StringTokenizer st;
        for(int i=0; i<T; i++){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            bw.write(dp[n][m] + "\n");
        }

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