[알고리즘] 백준 16195_1,2,3 더하기 9

백준 16195_1,2,3 더하기 9

• 1 에서 7까지 사용한 숫자 개수별 더해진 수 다 작성해봄
• 1 - 1, 2 - 1 1, 3 - 1 2 1, 4 - 0 3 3 1 ...
• 하다가 일단 찾긴 했는데 왜 인지 고민.
• 7을 5개로 하면 6을 4개로 한 거에 1붙이고, 5를 4개로 한 거에 2붙이고, 4를 4개로 한거에 3 붙인거.
  - 이걸 1~4개로 했을 때 더해진 수에 더하면 ㅇㅋ

import java.io.*;
import java.util.*;

public class Main {
	// 나눌 거랑 n의 최대값
    static final int MOD = 1_000_000_009;
    static final int MAX = 1000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

		// dp[i][j] = 합이 i이고 정확히 j개를 사용한 경우의 수
        long[][] dp = new long[MAX + 1][MAX + 1];
        // dpp[i][j] = dp[i][1] + dp[i][2] + ... + dp[i][j]
        long[][] dpp = new long[MAX + 1][MAX + 1];

        
        dp[0][0] = 1;

		// dp 갱신
        for (int i = 1; i <= MAX; i++) {
            for (int j = 1; j <= MAX; j++) {
                long value = 0;

                if (i - 1 >= 0) value = (value + dp[i - 1][j - 1]) % MOD;
                if (i - 2 >= 0) value = (value + dp[i - 2][j - 1]) % MOD;
                if (i - 3 >= 0) value = (value + dp[i - 3][j - 1]) % MOD;

                dp[i][j] = value;
            }
        }

        // dp 더한 dpp 갱신
        for (int i = 0; i <= MAX; i++) {
            for (int j = 1; j <= MAX; j++) {
                dpp[i][j] = (dpp[i][j - 1] + dp[i][j]) % MOD;
            }
        }

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            sb.append(prefix[n][m]).append('\n');
        }

        System.out.print(sb);
    }
}