갓갓류(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; }
|
다음에는 고민하는 시간을 더 많이 가져서 스스로 처음부터 끝까지의 해답을 찾고 싶다.
근데 바쁘다 ㅠㅠ
