[백준] 1, 2, 3 더하기 9 (16195번 JAVA)

[백준] 1, 2, 3 더하기 9 (16195번 JAVA)

---

[접근 방법]

15992번 [1, 2, 3 더하기 7] 문제와 아주 유사한 문제이다.

이전에는 각 수식이 몇개의 숫자로 이루어졌는지를 구해야했다면, 이번에는 몇개 이하의 수식 개수를 모두 더하면 된다.

 

15992번 [1, 2, 3 더하기 7] 문제 풀이는 다음과 같다.

https://notorious.tistory.com/176

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 7 (15992번 JAVA)

 

전반적인 풀이는 동일하고 마지막에 result 변수를 선언하여 m 이하의 수를 사용한 경우를 모두 더해주었다.

---

[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

        // 정수 i가 j개의 수로 이루어진 경우의 수 구하기
        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;
            }
        }
        
        for(int i=0; i<T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            // m 개 이하의 수를 사용한 경우의 수를 모두 더해준다.
            long result = 0;
            for(int k=1; k<=m; k++){
                result += dp[n][k];
            }
            bw.write(result % 1_000_000_009 + "\n");
        }

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