[백준] 2133번 타일 채우기 - C/C++
https://www.acmicpc.net/problem/2133
문제
3 ×N 크기의 벽을 2 ×1, 1 × 2 크기의 타일로 채우는 경우의 수를 구해보자.
입력
첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.
출력
첫째 줄에 경우의 수를 출력한다.
문제에서 주어진 힌트와 같이 2개 단위로 커질 때마다 그 타일을 이 전 타일들로 만들지 못하는 유일한 타일 배치가 2개씩 생기게 된다. 2개만 유일하게 3가지의 경우가 가능하다.
입력값으로 홀수가 주어지게 된다면 3*N 이 총홀수개의 단일 타일이 필요하게 되므로 만들 수 있는 경우의 수는 없다.
짝수가 들어올 경우 본인만의 유일한 타일 갯수 2개 , 3가지의 3*2 타일을 배치하고 (본인-2)를 배치하거나 3*4의 타일 2개를 배치하고 (본인-4)를 배치하거나... 가 된다. 이렇게 이 전 타일들을 먼저 구해 놓으면 타일을 만들 경우의 수를 모두 구할 수 있다.
#include <iostream>
#include <cstring>
using namespace std;
int N, sum = 0;;
int dp[31] = { 0 };
int main() {
cin >> N;
memset(dp, 0, sizeof(dp));
dp[2] = 3;
for (int i = 4; i <= 30; i += 2) {
dp[i] += 2;
dp[i] += 3 * dp[i - 2];
for(int idx = 4 ; idx <= i;idx+=2 )
dp[i] += 2 * dp[i - idx] ;
}
cout << dp[N] << "\n";
return 0;
}
처음에는 문제의 힌트를 안보고 3가지 경우의 수만 있는 줄 알고 제출했으나 틀렸다. 그렇게 4를 만들 수 있는 타일을 보고 4까지만 특별한 경우가 있는 줄 알고 재귀 형식의 코드와 반복문 형식의 코드를 모두 짰으나 틀렸다. 다시 곰곰이 생각해보다 2가 증가할 때마다 유일한 타일 배치가 생겨나는 것을 알고 코드를 짜서 맞게 되었다.
원래 이런 단순 점화식 문제는 잘 풀지 않는데 친구가 풀자고 하여 이번 기회에 접하게 되었다. 이런 단순 점화식 문제는 코드를 짜는 것보다 점화식만 구하면 코딩은 쉽다는 생각에 잘 풀지 않았는데 생각해낸 규칙을 점화식으로 만들고 그것을 또 코드로 옮기는 것이 아무 실수가 없진 않았다. 이러한 문제도 종종 연습해야겠다!