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

문제)

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1+2+1

1+3

3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력)

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

 

예제 입력)

3 4 7 10

 

4의 경우, 1+2+1, 1+3, 3+1 => 3가지

n=4일 때,

x+1 = n이 되는 경우 1앞에 올 수 있는 수는 2 또는 3 (연속으로 수가 올 수 없으므로 1은 제외함)

x+2 = n, 2 앞에 올 수 있는 수는 1 또는 3

x+3 = n, 3 앞에 올 수 있는 수는 1 또는 2

 

점화식으로 나타낸다면,

D[n][1]=D[n-1][2]+D[n-1][3]; //n을 만들기 위한 경우의 수 중, 마지막 피연산자가 1인 경우의 수

D[n][2]=D[n-2][1]+D[n-2][3];

D[n][3]=D[n-2][2]+D[n-3][1];

로 나타낼 수 있다.

 

단 n=0, 1, 2, 3일 때의 예외처리를 해주어야 한다.

1. 0을 만들 수 있는 경우의 수는 0개.

2. 1의 경우의 수는 마지막 피연산자가 1인 경우,

3. 2의 경우의 수는 마지막 피연산자가 2인 경우,

4. 3의 경우의 수는 마지막 피연산자가 1,2,3인 경우일 때 각각1가지씩 존재한다.

 

1.

D[0][1]=0;

D[0][2]=0;

D[0][3]=0;

 

2.

D[1][1]=1;

D[1][2]=0;

D[1][3]=0;

 

3.

D[2][1]=0;

D[2][2]=1;

D[2][3]=0;

 

4.

D[3][1]=1;

D[3][2]=1;

D[3][3]=1;

 

내가 짠 코드)

#include <iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); 

    int d[100001][4];
    int n;
    int t;

    cin>>t;

    d[0][1]=0;
    d[0][2]=0;
    d[0][3]=0;

    d[1][1]=1;
    d[1][2]=0;
    d[1][3]=0;

    d[2][1]=0;
    d[2][2]=1;
    d[2][3]=0;

    d[3][1]=1;
    d[3][2]=1;
    d[3][3]=1;

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

    while(t){
        cin>>n;
        cout<<(d[n][1]+d[n][2]+d[n][3])%1000000009<<'\n';  

        t--;
    }

}

 

그런데!

 int d[100001][4];

 

배열을 int로 선언해주니 큰 수를 입력할 때 오버플로우가 나타났다ㅠㅠ

반례인 경우로 99991 입력시

 

-42247586

라는 결과값이 나왔기 때문에

 long long d[100001][4];

 

int -> long long 으로 변경해주었더니 맞았다 !