[백준 20500번] [동적 계획법] Ezreal 여눈부터 가네 ㅈㅈ

재미있는 문제이다.

 

15는 3의 배수와 5의 배수 성질을 모두 가지고 있다. 즉 자릿수를 다 더한것이 3의 배수이고, 끝이 5아니면 0이다.

 

이러한 성질을 이용해서 DP로 풀어주면 쉽게 해결할 수 있다.

잘 생각해보면 N번째 자리는 무조건 1, 5로 시작할 수 밖에 없다.

마찬가지로 N-1번쨰 자리는 무조건 1, 5로 시작할 수 밖에 없다.

이를 활용하여 자릿수가 3이라는 것과 결부지어 생각해보자

 

"DP[n] : n번째 자리일 때 15배수의 갯수"로 잡았다고 하였을 때

 

맨 앞자리가 15로 시작하게 되면 뒤는 3의 배수이면서 자리가 n-2번쨰 자리를 만족하기만 하면 되므로 이는 DP[n-2]와 동치이다.

맨 앞자리가 51로 시작해도 마찬가지이다.

 

계속해서 수형도를 그려나가면서 가질 수 있는 경우의 수를 전부 다 파악하게 되면

DP[n] = sigma(2 * dp[n-k) + 1 ( 2<= k <= n - 1) 임을 구할 수 있다.

+1이 되는 경우는 수형도를 그려보면 이해할 수 있다.

 

대강

111 : dp[n - 3]

11511: dp[n-5]

11515:

1155: dp[n - 4]

15 : dp[n-2]

51 : dp[n - 2]

5511 : dp[n - 4]

55151:

55155:dp[n-5]

553 : dp[n - 3]

이런식으로 가지치기 해서 생각해주면 된다.

 

관계식을 잘 생각해보면 대칭적으로 나타나서 dp[n-k]가 각각 2번 등장하게 되는데

마지막 자리가 5가 나올 수 밖에 없다는 것을 잘 생각해보면 이 지점에서 대칭이 1번 깨진다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
typedef long long ll;

using namespace std;

int dp[1516];
int N;

int main(void){
    memset(dp, 0, sizeof(dp)); // 0 으로 초기화
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;

    cin >> N;
    if(N <= 3){
        cout << dp[N] << "\n";
        return 0;
    }

    int count = 4;

    while(count <= N){
        ll temp = 0;
        for(int i = 2; i <= count -2; i++){
            temp += 2 * dp[i];
            temp = temp % 1000000007;
        }
        dp[count] = temp + 1;
        count++;
    }

    cout << dp[N] << "\n";

    return 0;
}