BOJ 12928 트리와 경로의 길이

• 난이도 : Platinum 3
• solved ac class 8

풀이

주어진 조건은 총 정점의 수 $N$과 2-경로의 수 $S$개이고, 조금만 생각해 보면 2-경로의 수는 트리의 각 정점의 degree를 $d_i$ 라고 할 때 $\sum \binom{d_i}{2}$ 임을 쉽게 알 수 있다. 우리가 원하는 것은 $\sum d_i = 2N-2$, $\sum \binom{d_i}{2} = S$이다. Tree의 degree이므로 $0 < d_i < N$ 여야 할 것이다.

만약 이 조건이 전부라면, 우리는 degree에 대한 DP로 쉽게 문제를 풀 수 있다. 이 조건이 전부라는 것을 보이자. 즉, 임의의 degree sequence에 대해 $0 < d_i < n$이고 $\sum d_i = 2N-2$이면 반드시 대응하는 tree가 실제로 존재함을 보이면 된다. 증명을 매우 정확하게 적으려면 상당히 귀찮으므로, 대충 argument만 적어보자면…

$\sum d_i = 2N - 2$에서, $N$개의 자연수의 합이 $2N - 2$ 이므로 우리는 적어도 하나가 1임을 안다. 일반성을 잃지 않고 이를 $d_1$ 이라 하자. 이제, 1번을 리프로 생각하면, 리프가 달려 있는 parent node가 필요하다. 나머지 노드들 중 degree가 2 이상인 노드들 중 하나를 택하여 degree를 1 줄이고, 거기에 매달았다고 생각하면 $N-1$개의 degree의 합이 $2N - 4$ 이다. 이를 반복하여 귀납적으로 적용할 수 있다.

그러면, 풀이는 결국, $0 < d_i < N$ 인 자연수 $N$ 개의 합이 $2N - 2$이고, $\binom{d_i}{2}$의 합이 $S$가 될 수 있는지 여부를 확인하면 된다. 가장 간단한 방법은, dp[i][j][k] 를 i 개를 써서 합이 j 이고 dC2의 합이 k 인지를 boolean으로 기록하면 된다.

simple DP의 시간 복잡도는 총 $n$개의 $d$를 골라야 하고, 각각이 $n$개일 수 있으며, $nS$ 칸의 DP 테이블을 갱신하는 것이므로 무려 $O(n^3S)$ 이지만, $n = 50, S = 1000$ 이고 단순 연산이므로 그래도 넉넉하다.

사실 시간 복잡도에서 $n$을 하나 떼는 방법이 있지만, 현 제약에서는 이렇게 짜도 문제없이 잘 돌아간다 :)

Code

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

bool dp[55][105][1010];

int32_t main()
{
    usecppio
    int n, s; cin >> n >> s;
    int dsum = 2 * n - 2;
    int sqsum = s;
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int d = 1; d < n; d++)
        {
            for (int t = 0; t < dsum; t++)
            {
                if (t + d > dsum) break;
                for (int st = 0; st < sqsum; st++)
                {
                    int p = st + d * (d-1) / 2;
                    if (p > sqsum) break;
                    if (dp[i-1][t][st])
                        dp[i][t+d][p] = true;
                }
            }
        }
    }
    if (dp[n][dsum][s])
        cout << 1 << '\n';
    else cout << 0 << '\n';
}