개발 블로그

문제 링크 : www.acmicpc.net/problem/15990

문제

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

• 1+2+1
• 1+3
• 3+1

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

입력

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

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

접근 방법

문제의 조건에서 유의해야 할 점이 있다.

1) 1+3과 3+1 이 다름.

2) 같은 수를 두 번 이상 연속해서 사용할 수 없음.

일단 규칙을 찾기 위해 쭉 써보았다.

dp[1] = 1 (1)  (단일 숫자)

dp[2] = 1 (2) (단일 숫자)

dp[3] = dp[2]에 1을 더하는 경우 (2+1 -> 1가지)

          + dp[1]에 2를 더하는 경우 (1+2 -> 1가지)

          + dp[0]에 3을 더하는 경우 (0+3 -> 1가지)

          = 1 + 1 + 1 =3 

dp[4] = dp[3]에 1을 더하는 경우 (1+2+1 , 0+3+1 -> 연속 제외하고 2가지)

          + dp[2]에 2를 더하는 경우 (연속 제외하고 0가지)

          + dp[1]에 3을 더하는 경우 (1+3 -> 1가지)

          = 2 + 0 + 1 = 3

dp[5] = dp[4]에 1을 더하는 경우 (1+3+1 -> 연속 제외하고 1가지)

          + dp[3]에 2를 더하는 경우 (2+1+2, 0+3+2 -> 연속 제외하고 2가지)

          + dp[2]에 3을 더하는 경우 (2+3 -> 1가지)

          = 1 + 2 + 1 = 4

dp[6] = dp[5]에 1을 더하는 경우 (2+1+2+1, 0+3+2+1, 2+3+1 -> 연속 제외하고 3가지)

          + dp[4]에 2를 더하는 경우 (1+2+1+2, 0+3+1+2, 1+3+2 -> 3가지)

          + dp[3]에 3을 더하는 경우 (2+1+3, 1+2+3 -> 연속 제외하고 2가지)

          = 3 + 3 + 2 = 8

dp[7] = dp[6]에 1을 더하는 경우 (1+2+1+2+1, 0+3+1+2+1, 1+3+2+1  / 2+1+3+1, 1+2+3+1 -> 연속 제외하고 5가지)

          + dp[5]에 2를 더하는 경우 (1+3+1+2, 2+3+2 -> 연속 제외하고 2가지)

          + dp[4]에 3을 더하는 경우 (1+2+1+3, 0+3+1+3 -> 연속 제외하고 2가지)

          = 5 + 2 + 2 = 9

dp[n] = arr1[n] + arr2[n] + arr3[n] 으로 분할해서 더한다고 하자. (RHS의 각 배열은 +1, +2, +3 하는 경우이다.)

그러면

arr1[n] = arr2[n-1] + arr3[n-1]

arr2[n] = arr1[n-2] + arr3[n-2]

arr3[n] = arr1[n-3] + arr2[n-3] 

인 규칙을 찾을 수 있다. (위에 색칠해놓은 글씨를 보면 이해하기 쉽다.)

#include <iostream>

using namespace std;

long long dp[100001] = {0};
long long arr1[100001] = {0};
long long arr2[100001] = {0};
long long arr3[100001] = {0};


int main(){
    
        
    int TC; cin >> TC;

    arr1[3] = 1;    arr1[4] = 2;    arr1[5] = 1;
    arr2[3] = 1;    arr2[4] = 0;    arr2[5] = 2;
    arr3[3] = 1;    arr3[4] = 1;    arr3[5] = 1;
    
    dp[0] = 1; dp[1] = 1; dp[2] = 1;
    for(int i = 3; i<=5; i++) {dp[i] = (arr1[i] + arr2[i] + arr3[i]) % 1000000009;}
    
    for(int i = 6; i<=100000; i++){
        arr1[i] = (arr2[i-1] + arr3[i-1]) % 1000000009;
        arr2[i] = (arr1[i-2] + arr3[i-2]) % 1000000009;
        arr3[i] = (arr1[i-3] + arr2[i-3]) % 1000000009;
        dp[i] = (arr1[i] + arr2[i] + arr3[i]) % 1000000009;
    }
    
    
    for(int t = 0; t<TC; t++){
        
        int n;
        cin>>n;
        
        cout << dp[n] << "\n";
        
        
    }
    
    
    return 0;
}

주의할 점

int 형은 더할 때 범위가 넘어가므로 long long 자료형을 사용해야 한다.

그리고 for 문 안에서 arr1[], arr2[], arr3[] 을 구할 때도 Mod 연산을 적용해서 저장해야 한다.