[백준 12928] 트리와 경로의 길이

작성일 | In |

문제 링크

https://www.acmicpc.net/problem/12928

풀이

트리에서 길이가 2인 단순 경로의 개수는 노드$i$에 연결된 간선의 개수가 $d_i$개라고 할 때 $\sum {d_i \choose 2}$입니다.

$N$과 $S$의 크기가 매우 작습니다. 노드 $n$개로 이루어진 트리에서 $s$개의 단순 경로가 있을 수 있는지 모든 $NS$에 대해 확인해 볼 수 있습니다.

$D(n, s) = $ 트리를 이루고 남은 정점이 $n$개이고 현재까지 만들어진 경로의 개수가 $s$개로 만드는 것이 가능한지 로 DP를 정의합니다. 처음에는 크기 $2$짜리 트리를 하나 놓는다고 생각하고 시작합니다. 이때 경로의 개수는 $0$개입니다. $(D(N-2, 0))$ 그 뒤에는 degree가 $1$인 정점에(늘 존재함) $i$개의 정점을 붙여 경로의 개수를 ${i+1 \choose 2}$ 만큼 추가하여 $D(n-i, c+{i+1 \choose 2})$로 전이합니다. $D()$ 함수를 최대 $NS$번 방문하고 $i$가 $[1, n]$을 순회하기 때문에 $O(N^2S)$ 풀이입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>

int n, s, dp[55][1010];

void f(int n, int c){
    if(n == 0 && c == s) printf("1"), exit(0);
    if(n == 0 || dp[n][c] || c > s) return;
    dp[n][c] = 1;
    for(int i=1;i<=n;i++) f(n-i, c+i*(i+1)/2);
}

int main(){
    scanf("%d %d",&n,&s);
    f(n-2, 0);
    printf("0");
}