백준 도로 건설(14276)

axiom·2021년 4월 11일

도로 건설

1. 힌트

1) 도로를 짓는 순서와 도로의 방향을 강제해보자

2) 필요한 이전 정보는 놓을 수 있는 도로가 연결된 상태이다.

3) XOR연산을 이용하면 연결된 도로의 개수를 나타낼 수 있다.

2. 접근

1) 문제를 분해할 수 있을까?

우리는 문제에 주어진 조건에 맞게 도로를 건설하는 경우의 수를 구해야 한다. 가장 직관적인 접근 방법은 $N$ 개의 도시에 도로를 건설하는 경우의 수를 모두 나누어서 직접 시도해보고, 만들어낸 결과가 조건을 만족하는 경우만 세주면 된다. 물론 경우의 수를 잘 나누어서 어떠한 경우도 중복되지 않고, 포함되지 않는 경우가 없게 나누어야 한다.
경우의 수의 특성 상, 참조적 투명성이 만족되기 때문에 DP로 해결 가능할 것이다.

2) 순서를 강제할 수 있을까?

도로를 짓는 순서는 문제의 답과 상관이 없다. 그렇기 때문에 우리는 간단하게 번호가 작은 순서대로 경우의 수를 구하는 단계를 나누자.
경우의 수를 나누는 가장 좋은 방법은 역시 주어진 $N$ 개의 도시들을 $[i, N)\ (0 \le i\ <N)$ 의 범위를 가지는 부분연속수열로 나누어서 해결하는 것이다.
어떠한 형태의 점화식일지는 모르겠지만 $D[i]$ 는 $D[i + 1]$ 을 재귀 호출하는 형태일 것이다.

또한 $i$ 번째 도시마다 우리가 할 수 있는 선택은 도로를 연결하거나, 연결하지 않는 것 2가지 밖에 없다. 도로는 현재 도시 기준 왼쪽으로도 이을 수 있고 오른쪽으로도 이을 수 있고, 길이도 자유자재지만, 모두 오른쪽으로 짓는다고 방향을 강제해보자. 도로에는 방향성이 없기 때문에 경우의 수가 중복되어서 세지지 않는다.

이렇게 순서를 강제하면 존재할 수 있는 모든 도로를 도로의 시작점과 도로의 길이로 $w(here,\ length)$ 로 표현할 수 있다. 도로를 길이가 작은것부터 큰 것으로 짓는 과정을 시도한다고 하면 우리가 할 수 있는 선택은 단 2가지이다.
1. $w(here,\ length)$ 를 안 짓고 다음으로 넘어간다.
2. $w(here,\ length)$ 를 짓고 자기 자신을 재귀호출한다.

그런데 문제에서 모든 도시는 인접한 도로의 개수가 짝수개여야 한다고 하는데, $w(here, K)$ 도로에서 $w(here + 1, 1)$ 로 넘어갈 때, $here$ 을 지나치면 다시는 $here$ 로 도로를 인접하게 놓을 수 없음을 알면 $here$ 은 반드시 짝수개의 도로와 인접해야한다는 사실을 알 수 있다.

3. 구현

1) 다이나믹 프로그래밍

$N,\ K,\ M$ 이 주어지면 경우의 수는 언제나 같다. 그렇기 때문에 DP를 이용하여 중복계산을 최대한 없애줄 수 있다.

2) 비트필드를 이용한 다이나믹 프로그래밍

$here$ 에서 시작하는 도로를 지을 때, 도로의 반대편 끝에 있는 도시에도 인접한 도로의 수를 유지시켜야 재귀 호출 시 이전 정보로 넘겨줄 수 있으므로 비트마스킹을 사용하여 필드를 유지한다. 짝수 + 1은 홀수이고 홀수 + 1은 짝수이므로 XOR연산을 통해 구현하면 더 간단하다.

3) 시간 복잡도

존재할 수 있는 최대 부분 문제의 수는
$O(N \times (K + 1) \times (M + 1) \times 2^{K + 1})$ 이고, 함수 하나의 시간 복잡도는 O(1)이므로
$O(N \times (K + 1) \times (M + 1) \times 2^{K + 1})$ 이 된다.

4) 테스트 케이스

1 0 1
->1
간선을 하나도 놓지 않는 경우 한 개 밖에 없다.
30 30 8
->201860393
가장 큰 입력.
12 23 4
->62805419
아무거나 입력해 봤다.

public class Main {
	static int N, K;
	static int[][][][] cache;
	
	static final int MOD = 1000000007;
	
	// start번째 도시에서 length길이 이상의 도로를 m개 건설하려고 할 때,
	// [start, start + K]의 상태가 b일때 경우의 수
	static int dp(int start, int length, int m, int b) {
		// 맨 마지막 도시인 경우 더 이상 지을 간선이 없고, b에 나타난 도시들의 연결된 간선들의 개수가 모두 짝수여야 경우를 하나 찾음
		// 더 이상 지을 간선이 없는 경우, b에 나타난 도시들의 연결된 간선들의 개수가 모두 짝수여야 경우를 하나 찾음
		if (start >= N - 1 || m == 0) return m == 0 && b == 0 ? 1 : 0;
		// 간선의 길이가 K를 넘었거나, 범위를 벗어나면 다음 도시에 대해서 시도
		if (length > K || start + length >= N) return (b & 1) == 0 ? dp(start + 1, 1, m, b >> 1) : 0;
		if (cache[start][length][m][b] != -1) return cache[start][length][m][b];
		// length길이의 간선을 짓지 않는 경우
		int sum = dp(start, length + 1, m, b);
		// length길이의 간선을 하나 더 짓는 경우
		sum = (sum + dp(start, length, m - 1, b ^ 1 ^ (1 << length))) % MOD;
		return cache[start][length][m][b] = sum;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		cache = new int[N][K + 1][M + 1][1 << (K + 1)];
		for (int i = 0; i < cache.length; i++)
			for (int j = 0; j < cache[i].length; j++)
				for (int k = 0; k < cache[i][j].length; k++)
					Arrays.fill(cache[i][j][k], -1);
		System.out.println(dp(0, 1, M, 0));
	}

}