1. 문제 링크
https://www.acmicpc.net/problem/2133
2. 문제
요약
- 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 문제입니다.
- 입력: 첫 번째 줄에 1보다 크거나 같고 30보다 작거나 같은 N이 주어집니다.
- 출력: 첫 번째 줄에 경우의 수를 출력합니다.
3. 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public int getCaseNum(int n) {
if(n % 2 == 1) {
return 0;
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[2] = 3;
for(int i = 4; i <= n; i += 2) {
dp[i] = dp[i - 2] * dp[2];
for(int j = i - 4; j >= 0; j -= 2) {
dp[i] += dp[j] * 2;
}
}
return dp[n];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
br.close();
Main m = new Main();
bw.write(m.getCaseNum(n) + "\n");
bw.flush();
bw.close();
}
}4. 접근
- 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
- 만약 N이 홀수라면, 3xN 크기의 벽에 채워야 할 전체 칸 수는 홀수가 됩니다.
- 그러나 2x1 타일과 1x2 타일로 이 벽 전체를 채워야하는데 이 두 타일로는 짝수의 칸 수만 채울 수 있기 때문에 N이 홀수라면 경우의 수가 없어지게 됩니다.
- 각 N에서의 경우의 수를 나타내는 배열을 dp라고 정의합니다.
- 만약 N이 2인 경우에는 아래와 같은 경우의 수가 나올 수 있게 됩니다.
- 만약 N이 4인 경우에는 N이 2인 경우를 두 번 합한 것으로 볼 수 있습니다.
-
즉, N이 2일 때 3가지 경우의 수를 가졌으므로 N이 4일 때는 3 * 3 = 9가지의 경우의 수를 가집니다.
- dp[4] = dp[2] x dp[2]
-
그런데, N이 2인 경우를 두 번 합한 것으로는 만들 수 없는 경우의 수가 아래와 같이 존재합니다.
-
위 그림처럼 추가적인 경우의 수가 2가지 더 존재하기 때문에 N이 4일 때의 경우의 수는 11가지가 됩니다.
-
- 만약 N이 6인 경우에는 N이 2인 경우를 세 번 합한 것과 N이 4인 경우와 N이 2인 경우를 합친 것으로 볼 수 있습니다.
-
즉, N이 2인 경우를 세 번 합한 것이므로 이 때는 3 3 3 = 27가지의 경우의 수를 가집니다.
- dp[2] x dp[2] x dp[2] = 27
-
N이 4인 경우와 N이 2인 경우를 합칠 때는, 2인 경우가 왼쪽에 있는 경우와 오른쪽에 있는 경우가 있기 때문에 2인 경우와 4인 경우를 합친 11 * 3 = 33가지의 경우가 2번 나타나므로 66가지가 됩니다.
- dp[4] x dp[2]
- dp[2] x dp[4]
-
그런데, N이 4인 경우와 N이 2인 경우를 합치는 경우를 생각해보면 N이 2인 경우를 세 번 합한 것들을 포함하고 있습니다.
-
N이 4인 경우와 N이 2인 경우를 합치는 경우에서 N이 2인 경우를 세 번 합한 경우에 포함되지 않는 경우는 N이 4인 경우에 생기는 예외 케이스 2가지와 관련된 경우입니다.
-
그렇기 때문에 N이 4인 경우와 N이 2인 경우를 합치는 2가지 경우 중 한 가지에 대해서 우선 경우의 수를 구한 후에 예외 케이스 2가지에 대해서만 N이 2인 경우와 합쳐주면 N이 6일 때의 경우의 수가 나오게 됩니다.
- dp[6] = dp[4] x dp[2] + dp[2] * 2
-
그런데 N이 6인 경우에도 아래와 같이 2개의 예외 케이스가 존재합니다.
-
그렇기 때문에 N이 6인 경우의 경우의 수는 아래와 같습니다.
- dp[6] + dp[4] x dp[2] + dp[2] x 2 + 2
-
- N이 8인 경우 또한 아래와 같이 구할 수 있습니다.
- dp[8] = dp[6] x dp[2] + dp[4] x 2 + dp[2] x 2 + 2
- 위 경우들을 토대로 아래와 같은 점화식을 도출할 수 있습니다.
- dp[n] = dp[n - 2] x dp[2] + dp[n - 4] x 2 + dp[n - 6] x 2 + dp[n - 8] x 2 + ...
- 위 점화식을 토대로 dp 배열에 값을 채워나가며 답을 구합니다.
