[백준][DP] 1, 2, 3 더하기 5

1. 문제 주소

 

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

2. 문제

1, 2, 3 더하기 문제에서 같은 수를 연속해서 더하는 경우를 제외한 경우의 수를 구하는 문제이다.

n=4일 때를 보면

1+3, 3+1, 1+2+1 총 3가지 경우이다. 가장 마지막에 더해지는 숫자를 이용하여 2차원 배열을 만들면

d[4][1]=2 (+1로 끝나는 경우의 수)

d[4][2]=0 (+2로 끝나는 경우의 수)

d[4][3]=1 (+3로 끝나는 경우의 수)

이 된다.

n=5일 때

d[5][1] = d[4][2] + d[4][3]이 된다. 1이 연속적으로 더해지는 경우를 제외해야 하기 때문이다. 이런 식으로 규칙을 찾아은 후 코드를 작성하면 된다.

[백준][DP]1 2 3 더하기

3. 소스 코드

#include <iostream>
using namespace std;
 
long long d[100001][4];
long long num = 1000000009LL;
 
int main(void)
{
    int t;
    cin >> t;
    for (int i = 1; i <= 100000; i++)
    {
        if (i >= 1)
        {
            d[i][1] = (d[i - 1][2] + d[i - 1][3]) % num;
            if (i == 1)
                d[i][1] = 1;
        }
        if (i >= 2)
        {
            d[i][2] = (d[i - 2][1] + d[i - 2][3]) % num;
            if (i == 2)
                d[i][2] = 1;
        }
        if (i >= 3)
        {
            d[i][3] = (d[i - 3][1] + d[i - 3][2]) % num;
            if (i == 3)
                d[i][3] = 1;
        }
    }
 
    while (t--)
    {
        int n;
        cin >> n;
        cout << (d[n][1] + d[n][2] + d[n][3]) % num << '\n';
    }
 
    return 0;
}