[백준 15991] 1,2,3 더하기 6

문제 : 1,2,3 더하기 6

유형 : 다이나믹 프로그래밍

이 문제는 1,2,3 더하기 4, 5보단 조금 더 쉽고 재밌었던 문제였다.

더하기 식이 대칭이 되도록 만들면 되는 문제이다. 이를 어떻게 풀지 고민하다가 다이나믹 프로그래밍이므로 재귀적으로, 또한 합이 대칭을 만족해야 한다는 요점을 잡고 다시 보니 바로 눈에 보였다.

어떤 수 x가 있는데 이를 어떻게 대칭적이고 재귀적으로 풀 수 있을까?

바로 x에서 2, 4, 6을 빼고 반을 나눠 양쪽에 이어서 붙이면 된다.

ex) x => 1 + (x-2) + 1, 2 + (x-4) + 2, 3 + (x-6) + 3 

이렇게 빼면 된다. 근데 여기서 궁금증을 가지는 사람이 있을 수 있다.

ex) 4를 1 + 1 + 1 + 1로 만들 수 있는데 이는 어떻게 만들어지지...?

4도 똑같이 해보자. 단, 계속 1로 구성되어있으니 저게 만들어지는 과정만 보자.

먼저 4가 있다. 4는 2로 빼면 0보다 크거나 같다.   => 1 + (4-2) + 1 = 1 + 2 + 1

그 다음은 4에서 2를 뺀 나머지 2를 보자. 2는 2로 빼면 0보다 크거나 같다. => 1 + (2-2) + 1 = 1 + 0 + 1

근데 여기서 0은 있어도 되고 없어도 된다. 더하기에 영향이 없고 대칭을 망치지도 않는다.

따라서, 이를 가지고 점화식을 세워보자.

저 i의 범위를 만족하지 않으면 0이라고 생각하자. 그럼 한 줄로 간단하게 점화식을 수정해보면 아래와 같다.

여기에 모듈러 연산을 추가하면 되는 간단한 문제이다.

#include<iostream>
 
using namespace std;
 
typedef long long ll;
const ll mod=1000000009;
ll dp[100005];
 
int solve(int n)
{
    if(n==0)return 1;
    if(dp[n])return dp[n];
    ll sum=0;
    if(n-2>=0)sum=(sum+solve(n-2))%mod;
    if(n-4>=0)sum=(sum+solve(n-4))%mod;
    if(n-6>=0)sum=(sum+solve(n-6))%mod;
    return dp[n]=sum;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    dp[1]=1;
    dp[2]=2;
    dp[3]=2;
    
    for(;T--;)
    {
        ll input;
        cin>>input;
        cout<<solve(input)<<'\n';
    }
    
    return 0;
}