우리는 문제에 주어진 조건에 맞게 도로를 건설하는 경우의 수를 구해야 한다. 가장 직관적인 접근 방법은 개의 도시에 도로를 건설하는 경우의 수를 모두 나누어서 직접 시도해보고, 만들어낸 결과가 조건을 만족하는 경우만 세주면 된다. 물론 경우의 수를 잘 나누어서 어떠한 경우도 중복되지 않고, 포함되지 않는 경우가 없게 나누어야 한다.
경우의 수의 특성 상, 참조적 투명성이 만족되기 때문에 DP로 해결 가능할 것이다.
도로를 짓는 순서는 문제의 답과 상관이 없다. 그렇기 때문에 우리는 간단하게 번호가 작은 순서대로 경우의 수를 구하는 단계를 나누자.
경우의 수를 나누는 가장 좋은 방법은 역시 주어진 개의 도시들을 의 범위를 가지는 부분연속수열로 나누어서 해결하는 것이다.
어떠한 형태의 점화식일지는 모르겠지만 는 을 재귀 호출하는 형태일 것이다.
또한 번째 도시마다 우리가 할 수 있는 선택은 도로를 연결하거나, 연결하지 않는 것 2가지 밖에 없다. 도로는 현재 도시 기준 왼쪽으로도 이을 수 있고 오른쪽으로도 이을 수 있고, 길이도 자유자재지만, 모두 오른쪽으로 짓는다고 방향을 강제해보자. 도로에는 방향성이 없기 때문에 경우의 수가 중복되어서 세지지 않는다.
이렇게 순서를 강제하면 존재할 수 있는 모든 도로를 도로의 시작점과 도로의 길이로 로 표현할 수 있다. 도로를 길이가 작은것부터 큰 것으로 짓는 과정을 시도한다고 하면 우리가 할 수 있는 선택은 단 2가지이다.
1. 를 안 짓고 다음으로 넘어간다.
2. 를 짓고 자기 자신을 재귀호출한다.
그런데 문제에서 모든 도시는 인접한 도로의 개수가 짝수개여야 한다고 하는데, 도로에서 로 넘어갈 때, 을 지나치면 다시는 로 도로를 인접하게 놓을 수 없음을 알면 은 반드시 짝수개의 도로와 인접해야한다는 사실을 알 수 있다.
이 주어지면 경우의 수는 언제나 같다. 그렇기 때문에 DP를 이용하여 중복계산을 최대한 없애줄 수 있다.
에서 시작하는 도로를 지을 때, 도로의 반대편 끝에 있는 도시에도 인접한 도로의 수를 유지시켜야 재귀 호출 시 이전 정보로 넘겨줄 수 있으므로 비트마스킹을 사용하여 필드를 유지한다. 짝수 + 1은 홀수이고 홀수 + 1은 짝수이므로 XOR연산을 통해 구현하면 더 간단하다.
존재할 수 있는 최대 부분 문제의 수는
이고, 함수 하나의 시간 복잡도는 O(1)이므로
이 된다.
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));
}
}