[백준 155991번] 1, 2, 3 더하기 6 (C++)

문제링크 : https://www.acmicpc.net/problem/15991

15991번: 1, 2, 3 더하기 6

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

const int MOD = 1000000009;
int T, n;
ll dp[100001] = {0, 1, 2, 2, 3, 3, 6}; //초기화 6까지(3, 3)

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

    cin >> T;

    while(T--)
    {
        cin >> n;
        for(int i=7; i<=n; i++)
        {
            dp[i] = (dp[i-2] + dp[i-4] + dp[i-6])%MOD; //점화식 (양옆값 확인[1*2, 2*2, 3*2])
        }
        cout << dp[n] << "\n";
    }

    return 0;
}

 

사용하는 숫자는 1, 2, 3 뿐이고 대칭을 고려해야 하기 때문에 가웃데 숫자 기준 양옆에 1, 2, 3 중 어떤 값이 오는 지를 체크해주면 된다.

 

초기값으로는 dp[1 ~ 6] 까지 초기화를 진행해주어야 한다.

왜냐하면 11, 22, 33과 같이 특수한 대칭의 경우가 존재하는데 33의 경우가 6에 해당하기 때문이다.

따라서 1~6까지는 직접 카운팅하여 초기화를 진행해주고 이후 dp식은 i=7부터 갱신해준다.

 

앙옆에 오는 값들을 체크해보면 다음과 같은 내용을 알 수 있다.

양옆 1 -> 가운데 값 = N - (1*2)

양옆 2 -> 가운데 값 = N - (2*2)

앙옆 3 -> 가운데 값 = N - (3*2)

 

위와 같이 (현재 위치 - 양옆 수치)를 하여 가운데 값을 구할 수 있고, 이를 점화식으로 바꾸면 아래와 같다.

(dp[i] = dp[i-2] + dp[i-4] + dp[i-6])

 

그리고 주의해야할 것은 N의 범위는 10만이지만 전의 값을 계속 참고해서 누적하여 더하기 때문에 값의 수치는 int 범위를 넘어설 수 있다.

따라서 dp 배열은 long long으로 선언해주어야 한다.