POLY (중상, p. 264)

처음에는 ‘단조’ 조건 없이 만들 수 있는 모든 block의 경우의 수를 구한 다음에 ‘단조’ 조건을 고려해보려고 했다. 하지만, 이 방법으로는 답을 구할 수 없었다. 애초에 ‘단조’ 조건이 없는 경우의 수는… 구할 수 있는 건지 아직 잘 모르겠다. (아무래도 안되는 것 같긴 하다.)

그래서 한참 고민하다가 책에서 ‘단조’ 조건에 의해 층마다 block을 몇 개 사용할지 정하면, 전부다 붙여서 밀어넣기만 하면 된다는 힌트를 보고 다시 문제를 풀어보려 했다.

일단, x층에서 i개의 block을 쓰고, x-1층에서 j개의 block을 쓴다면, 이때 두 층에서만 만들어지는 경우의 수는 (i+j-1)이다. (그림을 그려보면 쉽게 알 수 있다.)

이제 대충 f(x,…)와 f(x-1,…)간의 관계를 그리면 되는데, 이게 생각보다 쉽지 않았다.

상태 공간을 어떻게 잡을지 육아하는 중간중간에 한참을 고민했는데, 애들 재우고 컴퓨터 앞에 앉아서 1시간쯤 더 고민을 한 끝에 답을 낼 수 있었다.

일단은 3층을 쌓는 경우를 적어봤다.

1, 2 → (1+2-1)가지

1, 1, 1 → (1+1-1) * (1+1-1)가지

2, 1 → (2+1-1)가지

3 → 1가지

그 다음 4층을 쌓는 경우를 적어봤다.

1, 3 → 3가지

1, 2, 1 → 4가지

1, 1, 2 → 2가지

1, 1, 1, 1 → 1가지

2, 1, 1 → 2가지

2, 2 → 3가지

3, 1 → 3가지

4 → 4가지

그 다음 3층과 4층과의 연관성이 어디에 있는지 보려고 4층의 모든 경우의 수에서 3층의 경우의 수를 색칠해봤다.

1, 3 → 3가지

1, 2, 1 → 4가지

1, 1, 2 → 2가지

1, 1, 1, 1 → 1가지

2, 1, 1 → 2가지

2, 2 → 3가지

3, 1 → 3가지

4 → 4가지

그랬더니 눈에 보이는 부분이 있었는데, 3층의 경우의 수 다음에 4층을 완성하는 방법은 뒤에 1을 추가하는 방법 밖에 없었다.

그럼 1을 추가할 때 이전 층에서 block을 j개 사용한다면, 그 경우의 수를 f(x-1,j) * (j+1-1)라고 할 수 있을텐데라고 생각했다. (여기서 f(x-1,j)는 x-1층에서 마지막에 j개의 block을 사용한 경우의 수이다.)

그렇게 따져보니 방금 4층에서 마지막에 1개의 block을 사용하는 방법은 f(4,1)로 나타낼 수 있었고, f(4,1) = f(3,1)*1 + f(3,2)*2 + f(3,3)*3 으로 표현할 수 있었다.

그래서 아래와 같이 점화식을 구할 수 있었다.

for(int i=1; i<=x-r; i++) {
    f(x,r) += f(x-r,i) * (i+r-1);
}

이 문제의 난이도를 ‘상’으로 하고 싶었지만, 앞으로 나올 정말 어려운 문제들을 위해 ‘중상’으로 분류했다. 층마다 block을 여러개 붙여서 넣기만 하면 된다는 힌트가 결정적이긴 했지만, 그 이후에 상태 공간을 만들 때에도 꽤나 난이도가 높았는데 그 부분은 혼자해결 할 수 있었으니 완전 ‘상’ 문제로 분류하긴 힘들 것 같다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e7;
bool chk[101][101];
ll dp[101][101];
int f(int x, int r) {
    if(x==r) return 1;
    if(chk[x][r]) return dp[x][r];
    chk[x][r] = true;
    ll & ret = dp[x][r];

    for(int i=1; i<=x-r; i++) {
        ret += (ll)(i+r-1)*f(x - r, i);
        ret %= M;
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n; cin >> n;
        ll ans=0;
        for(int i=1; i<=n; i++) {
            ans += f(n,i);
            ans %= M;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

문제 아래에 있는 댓글들을 보니 이런 문제의 정답률이 70%나 된다는 것에 사람들이 놀라는 것 같다.

근데 DP문제들을 풀어보면 알겠지만, DP는 점화식만 구하면 코드에서 답을 틀리기가 상당히 힘들다.