백준 15990번 1,2,3 더하기 5 (C++)

문제 링크 : www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

이 문제는 '같은 수를 두 번 이상 연속해서 사용하면 안된다'라는 조건 때문에

여타 다른 DP문제처럼 [n-1]+[n-2]+[n-3]의 점화식으로는 풀 수 없다.

결국 같은 수를 두 번 이상 연속사용을 방지하려면, 어떤 숫자의 계산식에 마지막에 쓰인 숫자가 무엇인지를 생각해봐야한다.

때문에 이 문제는 마지막에 쓰인 숫자(1, 2, 3)들을 구분해서 저장할 2차원 배열로 접근해야한다.

 

문제 풀이는 아래의 코드를 보면 쉽게 이해할 수 있으므로, 구체적인 설명은 생략한다.

 

#include <iostream>
#define mod 1000000009
using namespace std;

long long arr[1000001][4];
const int limit = 100000;

void Input(){
    arr[1][1] = 1, arr[1][2] = 0, arr[1][3] = 0;
    arr[2][1] = 0, arr[2][2] = 1, arr[2][3] = 0;
    arr[3][1] = 1, arr[3][2] = 1, arr[3][3] = 1;
    for(int i=4; i<=limit; i++){
        arr[i][1] = arr[i-1][2] + arr[i-1][3];
        arr[i][2] = arr[i-2][1] + arr[i-2][3];
        arr[i][3] = arr[i-3][1] + arr[i-3][2];
        arr[i][1] %= mod;
        arr[i][2] %= mod;
        arr[i][3] %= mod;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t = 0, temp = 0;
    cin >> t;
    Input();
    while(t--){
        cin >> temp;
        cout << (arr[temp][1] + arr[temp][2] + arr[temp][3]) % mod << "\n";
    }
    return 0;
}