1, 2, 3 더하기 5_ 백준15990

15990

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
단, 같은 수를 두 번 이상 연속해서 사용해서는 안됩니다.

1,2,3더하기의 심화버전인 문제이다. 

n이 주어졌을 때 1,2,3만의 합으로 구하는 것이며, 같은 수를 두번 이상 연속해서 사용하면 안된다는 조건이 추가되었다.

 

그렇다면, 같은 수인지 아닌지 확인하기 위한 추가적인 절차가 필요하다.

이를 위해서 정수의 값을 저장할 부분을 이차원 리스트로 만들었다.

 

즉, n이 주어졌을 1,2,3의 합으로 나타내는 경우의 수를 d[n]이라 하면

• d[n] = d[1] + d[n-1]
• d[n] = d[2] + d[n-2]
• d[n] = d[3] + d[n-3]

이므로, n이 주어졌을 때 위의 세 사례로 나누어 계산을 진행하는 것이다.

두번이상 연속되지 않는 1,2,3의 합으로 나타내는 경우의 수를 d[n]이라 하면

그 뒤에 쓴 수 (1,2,3)와 겹치지 않는 수로 더해서 계산하면 된다.

• d[n][1] = d[n-1][2] + d[n-1][3]
• d[n][2] = d[n-2][1] + d[n-2][3]
• d[n][3] = d[n-3][1] + d[n-3][2]

여기서 조금 헤멘건 리스트의 자료형을 int로 했던건데, 아마 int에 담을 수 있는 수보다 커져서 문제가 생겼던 것 같다.

자료형을 적절히 큰 것을 사용하니 해결된 문제이므로 주의해야 할 것 같다.

//15990 123더하기

#include <stdio.h>
long long d[1000001][4];
const long long MOD = 1000000009LL;
int main(void)
{
    d[1][1] = d[2][2] = 1;
    d[3][1] = d[3][2] = d[3][3] = 1;

    for (int i = 4; i <= 100000; i++)
    {
        d[i][1] = (d[i - 1][2] + d[i - 1][3]) % MOD;
        d[i][2] = (d[i - 2][3] + d[i - 2][1]) % MOD;
        d[i][3] = (d[i - 3][2] + d[i - 3][1]) % MOD;
    }

    int count;
    scanf("%d", &count);
    while (count--)
    {
        int a;
        scanf("%d", &a);
        printf("%lld\n", (d[a][1] + d[a][2] + d[a][3]) % MOD);
    }
}