15990 실버 1) 1, 2, 3 더하기 5 DP

 

풀이: 어떤 수가 마지막을 이루고 있는지를 확인한다

 

만약 1로 끝나는 경우라면 arr[i-1][2] + arr[i-1][3]인 2로 끝나는 것과 3으로 끝나는 값을 서로 더해주면 된다.

 

#include <iostream>

using namespace std;

int main() {

    // 입력 출력 속도 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    
    // n값 입력 받기
    cin >> n;
    
    // 2차원 배열 선언 (최대 1000000까지 크기, 4개의 열)
    // arr[i][1], arr[i][2], arr[i][3]은 각각 i를 1, 2, 3으로 나눈 경우의 값을 저장
    // long long 자료형을 사용하여 큰 값을 처리할 수 있도록 설정
    long long arr[1000001][4] = {0,};
    
    // 초기값 설정: n이 1일 때, 1을 만드는 유일한 방법은 1을 사용하는 것
    arr[1][1] = 1;
    
    // n이 2일 때, 2를 만드는 유일한 방법은 2를 사용하는 것
    arr[2][2] = 1;
    
    // n이 3일 때, 1, 2, 3을 사용하는 방법이 모두 가능
    arr[3][3] = 1;
    arr[3][2] = 1;
    arr[3][1] = 1;
    
    // n이 4 이상일 때, i를 1, 2, 3의 조합으로 나누는 경우의 수 계산
    for(int i = 4; i <= 1000000; i++) {
        // i를 1로 나눈 경우는 i-1을 2 또는 3으로 나눈 경우의 수를 합한 것
        arr[i][1] = arr[i-1][2] + arr[i-1][3];
        
        // i를 2로 나눈 경우는 i-2를 1 또는 3으로 나눈 경우의 수를 합한 것
        arr[i][2] = arr[i-2][3] + arr[i-2][1];
        
        // i를 3으로 나눈 경우는 i-3을 1 또는 2로 나눈 경우의 수를 합한 것
        arr[i][3] = arr[i-3][2] + arr[i-3][1];
        
        // 각 경우의 수를 1000000009로 나눈 나머지로 저장하여 overflow 방지
        arr[i][1] %= 1000000009;
        arr[i][2] %= 1000000009;
        arr[i][3] %= 1000000009;
    }
    
    // 테스트 케이스의 개수 n만큼 반복
    for(int i = 0; i < n; i++) {
        int t;
        
        // 테스트 케이스에서 숫자 t 입력 받기
        cin >> t;
        
        // t를 1, 2, 3의 조합으로 나눈 모든 경우의 수 계산 후 출력
        // 결과를 1000000009로 나눈 나머지를 출력
        cout << (arr[t][1] + arr[t][2] + arr[t][3]) % 1000000009 << '\n'; 
    }

}