BOJ 12928 - 트리와 경로의 길이 [Java]

 

 

문제

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

정수 $N$과 $S$가 주어지면, 정점의 개수가 $N$개이며 길이가 $2$인 단순 경로의 수가 $S$개인 트리를 만들 수 있는지 판별하는 문제다. 두 경로가 서로 방향만 다르고 지나는 점이 동일하면 같은 경로이다.

 

풀이

정점의 개수가 $n$개이고 길이가 $2$인 단순 경로의 수가 $s$개인 트리가 있다고 가정하자.

이 트리에서 차수가 $k$인 정점에 새 정점을 이어붙이면, 단순 경로의 수는 $s+k$가 된다.

구체적으로, 정점의 수가 $n$이고 길이가 $2$인 단순 경로의 수가 $s$이며, 차수가 $k$인 정점이 존재하는지 여부는 배낭으로 쉽게 알 수 있다.

 

위 정의대로 $d[n][k][s]$를 정의하면, $d[n][k][s] = 1$일 때

$d[n+1][k+1][s+k] = 1$

$d[n+1][1][s+k] = 1$

이다.

 

import java.util.*;
import java.io.*;

public class Main {
    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int nextInt() { return Integer.parseInt(st.nextToken()); }
    static void newLine() throws Exception { st = new StringTokenizer(br.readLine()); }

    public static void main(String[] args) throws Exception {

        newLine();
        int N = nextInt(), S = nextInt();

        boolean[][][] d = new boolean[N+1][N][S+1];
        if(N < 3) {
            bw.write("0");
            bw.close();
            return;
        }
        d[3][1][1] = true;
        d[3][2][1] = true;
        boolean ans = N==3&&S==1 ? true : false;
        for(int n=3;n<N;n++) for(int k=1;k<n;k++) for(int s=1;s<=S;s++) if(d[n][k][s] && s+k<=S) {
            d[n+1][k+1][s+k] = true;
            d[n+1][1][s+k] = true;
            if(n+1==N && s+k==S) ans = true;
        }
        bw.write((ans ? "1" : "0"));

        bw.close();
    }

}