DP > 1, 2, 3 더하기 5 (15990번)

문제

---

풀이

자료형 이씨...

다 구현했는데 d배열을 int로 선언해서 틀렸다..

long long으로 바꾸니까 되네...

이게 오버플로우 고려를 해줬어야 하는데 안해서 난거 같다.

일단 풀이과정 설명 먼저 하고 오류 난 이유도 적어야지

 

우선 여기서는 이전에 풀었던 "1, 2, 3 더하기" 문제와 다른 점이 있다.

바로 숫자가 연속되게 올 수는 없다는 것이다.

예를 들어 n이 4일 때 1+1+2는 안되지만 1+2+1은 되는 것이다.

 

이 문제도 1, 2, 3 더하기 문제와 동일하게 맨 마지막에 오는 숫자에 집중을 해준다. 그렇게 문제를 쪼갤거니까~

근데 달라지는 것은 맨 마지막 숫자에 따라서 앞에 올 수 있는 숫자가 달라진다는 것이다.

맨 마지막 숫자가 1이면? 앞에는 2, 3만 가능하고, 2이면 1, 3만 가능하고 3이면 1, 2만 가능하다.

이걸 표현하려면 1차원 배열로는 표현할 수 없다!

그래서 여기에서는 2차원 배열로 표기한다.

 

d[i][j] = 맨 마지막 수가 j이고, i를 1, 2, 3으로 표현할 수 있는 방법의수

그럼 예시로 d[3][1]은 맨 마지막 수가 1이면서 3을 표현할 수 있는 방법의 수가 되는 것이다.

그럼 j에는 뭐가 올 수 있겠는가?

1, 2, 3만 가능한 것이다! -> 나열할 수 있는 수가 1, 2, 3이니까 j도 마찬가지이다!

그럼 n을 표현할 수 있는 총 방법의 수는 무엇이겠는가? -> d[i][1] + d[i][2] + d[i][3] 이다!

 

이제 점화식을 세워보자.

만약에 j가 1이라면 경우의 수는 어떻게 되는가?

ㅇ+ㅇ+ㅇ+ ... +ㅁ+1  -> 이런식으로 표현되는데 ㅁ에는 2, 3만 가능하겠지?

그럼 d[i][1] = d[i-1][2] + d[i-1][3]이 될 것이다.

(i를 표현할 때 맨 마지막 수가 1이니까 남은 수는 i-1이고, i의 마지막 수, 즉 i-1 바로 뒤의 수가 1이니까 i-1의 맨 마지막 수에는 2와 3만 올 수 있는 것이다.)

 

똑같이 생각하면 최종 점화식은 이렇게 된다.

 

d[i][1] = d[i-1][2] + d[i-1][3]

d[i][2] = d[i-2][1] + d[i-2][1]

d[i][3] = d[i-3][1] + d[i-3][2]

 

그리고 이 문제는 초기화도 중요한데, 점화식에 i-3 까지 등장하기 때문에 난 i가 3일때까지는 초기값을 부여했다.

그리고 그냥 저렇게만 하면 배열에 저장할 때 오버플로우가 발생할 수 있다!

따라서 배열의 자료형은 int가 아닌 long long으로 선언하고, 저 3개의 점화식을 구할 떄도 틈틈히 나머지만을 저장해준다,

그리고 마지막에 출력할 떄도 나머지를 출력해서 혹시라도 발생할 수 있는 오버플로우의 경우를 예방해준다.

(이걸 안해서 계속 틀렸다..ㅠㅠ)

---

코드

#include <iostream>
#include <stdio.h>
#define MAX 100001
#define rem 1000000009

long long d[MAX][4];

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    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 k=4;k<MAX;k++)
    {
        d[k][1]=(d[k-1][2]+d[k-1][3])%rem;
        d[k][2]=(d[k-2][1]+d[k-2][3])%rem;
        d[k][3]=(d[k-3][1]+d[k-3][2])%rem;
    }
    
    int n, t;
    cin>>t;
    
    for(int i=0;i<t;i++)
    {
        cin>>n;
        printf("%d\n",(d[n][1]+d[n][2]+d[n][3])%rem);
    }
    
    
    return 0;
}