AtCoder : ABC 178 D - Redistribution

atcoder.jp/contests/abc178/tasks/abc178_d

D - Redistribution

이 문제 역시 대표적인 형식의 DP문제이다.

 

앞선 포스팅에서 살펴본 간단한 DP문제들은 이전 히스토리에서 한 개나 두 개 정도를 참조하여 현재의 값을 구하였다 (기본 피보나치 수열은 이전 값 2개를 참조하여 현재의 값을 구한다). 하지만 이번에는 꽤나 많은 값을 가져와야 한다.

수열의 합이 S가 되고, 각 수는 3이상이므로 첫 수는 항상 3부터 시작해서 따져봐도 좋다. 그리고 물론 S가 3보다 작다면 답은 0이다.

위의 그림은 S가 7일 때와 S가 10일 때를 다루고 있다. S가 7일 때는 예제에서와 같이, 3가지 경우가 있다. 3으로 시작했다면 다음 수가 4라면 합산하여 7을 만들 수 있다. 4로 시작했다면 다음수가 3 이오고 7이 된다. 5로는 시작할 수 없다. 3보다 작은 수가 올 수는 없기 때문이다. 그리고 7은 가능하다. 즉, S자신은 항상 포함되게 된다.

그런데 그 S=10일 때를 보자. S가 10일 때, 여러가지 경우가 있겠지만 그림과 같은 3가지 경우는 DP[7]일 때의 경우에 3만 끝에 더해준 꼴이 된다. 즉 DP[7]을 그대로 합산 가능한 것이다. 

위의 그림과 같이, S=10일 때, 3부터 시작하여 7로 시작하는 경우까지(8부터는 안된다. 2가 올순 없으므로) 생각해볼 수 있다. 그리고 10인 경우도 놓치지 않는다. 3으로 시작했다면 DP[7]의 경우가 되고, 4로 시작했다면 DP[6]의 경우가 된다. 즉 S가 주어졌을 때, DP[3]부터 DP[S-3]까지 모두 합해주고 1을 더해주면 (자기 자신) 되는 것이다. 

 

<주요 내용>

다이나믹 프로그래밍, 동적계획법, 재귀함수, 메모이제이션

 

<코드>

전형적인 DP형식으로 풀이할 수도 있지만, 필자는 문제 풀이 당시 이 방법이 생각나서 재귀+메모로 풀었다.

#include <iostream>
#define endl '\n'
using namespace std;
const int num=2e3+1;
int s,dp[num],mod=1e9+7;
int solve(int n){
    int ret=0;
    if(dp[n]!=1)return dp[n];
    for(int i=3;i<=n-3;++i)ret=(ret+solve(i))%mod;
    dp[n]=(ret+dp[n])%mod;
    return dp[n];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>s;
    fill(dp,dp+s+1,1);
    for(int i=0;i<3;++i)dp[i]=0;
    cout<<solve(s)%mod<<endl;;
    return 0;
}