Ethan Hur's blog

백준 온라인 저지 #2718 타일 채우기

2017-11-29

갓갓류(rhs0266)에게 또 문제를 추천받아 풀었다. (사실 풀이를 직접 생각해내진 못했다 ㅋㅋ)

bit DP 를 이용하여 푸는 문제였는데 되게 점화식 모델링에 어려움을 겪었다.

이 문제의 핵심 포인트는 i번째 열에 채워졌냐/안채워졌냐 를 기준으로 16가지 케이스로 구분을 하고

또 이를 5개의 경우만 생각해도 된다는(다른 상태는 불가능) 것을 생각해내는 것이었다.

나의 경우에는 i번째 열에 16가지 케이스로 구분을 한다는 걸 떠올리지 못해서 (사실 핵심 아이디언데 말이다 ㅋㅋㅋ) 힌트를 받았다.

위에 것만 알면 그냥 쉬운 DP 문제이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
int f[10000][5];
int T, arr[1001], i, j;
int getMax() {
int max = -1;
for (int i = 0; i < T; i++) {
if (max < arr[i])
max = arr[i];
}
return max;
}
int main() {
scanf("%d", &T);
for (i = 0; i < T; i++) {
scanf("%d", &arr[i]);
}
f[0][0] = 1;
f[0][1] = 0;
f[0][2] = 0;
f[0][3] = 0;
f[0][4] = 0;
int max = getMax();
for (j = 1; j <= max; j++) {
f[j][0] = j == 1 ? 1 : f[j - 2][0] + f[j - 1][0] + f[j - 1][1] + f[j - 1][2] + f[j - 1][3]; // 다 차있을 경우
f[j][1] = f[j - 1][0] + f[j - 1][3]; // 위의 두개
f[j][2] = f[j - 1][0] + f[j - 1][4]; // 중간 2개
f[j][3] = f[j - 1][0] + f[j - 1][1]; // 밑의 2개
f[j][4] = f[j - 1][2]; // 양 끝
}
for (i = 0; i < T; i++) {
printf("%d\n", f[arr[i]][0]);
}
return 0;
}

다음에는 고민하는 시간을 더 많이 가져서 스스로 처음부터 끝까지의 해답을 찾고 싶다.

근데 바쁘다 ㅠㅠ

Tags: PS