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

문제

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

리뷰

n을 1,2,3의 합으로 나타내는 경우의 수를 구해봤을 때, 규칙이 있는지 정수 8까지 경우를 써봤다.

정수 n이 3의 배수인 경우에는 이전 합에서 * 2를 하면 되는줄 알았는데, 점화식이 틀렸다.

 

다른 분 풀이를 보니까 n을 때, 마지막 수가 i인 경우를 따져봤다. (i는 1, 2, 3 )

연속으로 같은 숫자를 쓸 수 없음을 이용한 것이다.

정수 n 이 주어지면, 마지막 수가 i인 경우 (i는 1, 2, 3 ) D[n] [1] , D[n] [2] , D[n] [3] 으로 식을 세우는 것이다.

왜냐하면 1+1+1 처럼, 연속된 수는 못오기 때문이다.

1 앞에는 2, 3만 올 수 있다.

2 앞에는 1, 3만 올 수 있다.

3 앞에는 1, 2만 올 수 있다.

n	D[ n ][ 1 ]	D[ n ][ 2 ]	D[ n ][ 3 ]	합계
1	1개	0	0	1
2	0	1개	0	1
3	1개 (2+1)	1개 (1+2)	1개 (3)	3
4	2개 (1+2+1, 3+1)	0	1개 (1+3)	4
5	1개 (1+3+1)	2개 (3+2, 2+1+2)	1개 (2+3)	4
6	3개 (2+1+2+1, 3+2+1, 2+3+1)	3개(1+2+1+2, 1+3+2, 3+1+2)	2개(2+1+3, 1+2+3)	8
7	5개	2개	2개	9
8	4개	4개	2개	10

n = 6인 경우를 보자.

 

D[6] [1] 을 구하기 위해서는 6에서 1을 뺀 D[5] 라인을 살펴봐야 한다.

왜냐하면 1 앞에는 2와 3이 올 수 있으므로, n에서 1을 뺀 5의 경우의 수를 봐야 한다.

 

2가 마지막에 오는 경우의 수 D[5] [2] 와 + 3이 마지막에 오는 경우의 수 D[5] [3] 를 더하면 D[6] [1] 이 된다.

2가 마지막에 오는 경우의 표현들 D[5] [2] 뒤에 +1 을 해주면 6이 된다.

3이 마지막에 오는 경우의 표현들 D[5] [3] 뒤에 + 1 해주면 6이 된다.

 

마찬가지로 D[6] [2] 를 구하기 위해서는 6에서 2를 뺀 D[4] 라인을 살펴봐야 한다.

왜냐하면 2 앞에는 1과 3이 올 수 있는데, 4에서 1과 3으로 끝난 경우의 수들을 봐야 하기 때문이다.

 

그래서 1이 마지막에 오는 경우의 수 D[4] [1] 과 3이 마지막에 오는 경우의 수 D[4] [3] 를 더하면 D[6] [2] 이 된다.

 

점화식은 아래와 같다.

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]

코드

#include <stdio.h>
#define MODNUM 1000000009
using namespace std;


long long D[100001][4]; 

long long sum_case(int num){

    int i = 0;

    for(i=4; i <= num; i++){
        D[i][1] = (D[i-1] [2] + D[i-1] [3]) % MODNUM;
        D[i][2] = (D[i-2] [1] + D[i-2] [3]) % MODNUM;
        D[i][3] = (D[i-3] [1] + D[i-3] [2]) % MODNUM;
    }

    return (D[num][1] + D[num][2] + D[num][3])  % MODNUM;

}

int main(void){

    freopen("input.txt", "rt", stdin);

    int test_case, n = 0, num = 0;

    D[1][1] = D[2][2] = 1;

    D[3][1] = 1;
    D[3][2] = 1;
    D[3][3] = 1;

    scanf("%d", &test_case);

    while(test_case--){
        scanf("%d", &num);
        printf("%lld\n", sum_case(num));
    }

    return 0;
}

마지막으로 mod 연산 때문에 틀려서 참고한 코드가 있다.

sum_case() 의 반환값도 long long, D배열의 반환값도 long long으로 해야 맞출 수 있었다.