1, 2, 3 더하기 9 16195

https://www.acmicpc.net/problem/16195

규칙을 찾는게 어렵다 검색해서 규칙을 알았는데 왜 그렇게 되는건지 모르겠다

위의 그림처럼 1, 3, 6 더하면 10 이 된다

위의 그림처럼 1, 2, 4 더하면 7 이 된다

    처음에는 dp 배열을 구성하는 데 필요한 시간 복잡도가 O(n^2)입니다. 왜냐하면 2중 for 루프를 통해 n의 크기까지 모든 가능한 조합에 대한 결과를 계산하기 때문입니다.

    그 다음에는 테스트 케이스의 수(T)에 대해 반복문을 실행합니다. 각 테스트 케이스마다 최악의 경우 O(n) 시간이 소요됩니다. 이 부분의 시간 복잡도는 따라서 O(T*n)입니다.

따라서 전체 시간 복잡도는 dp 배열 구성 비용과 각 테스트 케이스를 처리하는 비용을 합친 것이므로 O(n^2 + T*n)이라고 할 수 있습니다. 이는 입력 크기 n과 테스트 케이스의 수 T에 따라 결정됩니다.

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

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

        long[][] dp = new long[1001][1001];

        dp[1][1] = 1;
        dp[2][1] = 1;
        dp[2][2] = 1;
        dp[3][1] = 1;
        dp[3][2] = 2;
        dp[3][3] = 1;//3 이란 숫자를 만드는데 3개의 숫자를 사용하는경우 1

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

        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        String[] input;

        int n = 0;//0~1000
        int m = 0;// n <=
        long answer = 0;
        for (int i = 0; i < T; i++) {
            input = br.readLine().split(" ");
            n = Integer.parseInt(input[0]);
            m = Integer.parseInt(input[1]);

            for (int j = 0; j <= m; j++) {
                answer = (answer + dp[n][j]) % 1000000009;
            }
            System.out.println(answer);
            answer = 0;

        }

    }
}