백준 2133 c++ "타일 채우기" -PlusUltraCode-

https://www.acmicpc.net/problem/2133

 

[필자 사고]

동적프로그래밍의 대표저인 타일 채우기 문제이다.

다만 이 문제만의 특별한 점은 세로의 크기가 3이라는 점이다.

이러한 특성으로 인해 N의 값이 홀수이면 만들 수 있는 경우의 수가 없다.

또한 도중 보이는 특이케이스 경우의 수도 있다.

기존 방식에서 특이케이스 경우의 수도 더해줘야 해당 문제를 풀 수 있다.

처음 문제를 풀 때는 특이케이스에 대해 생각도 못했었는데

사고를 확장시켜 준 문제이다.

[코드 해설]

2. 입력 처리 (Input 함수)

사용자로부터 정수 N을 입력받고, 이를 저장할 벡터 dp를 동적으로 할당한다. 벡터의 크기는 N+1로 설정하여, 인덱스 N까지 접근할 수 있도록 한다.

3. 동적 프로그래밍을 이용한 문제 해결 (Game_Start 함수)

이 함수는 미리 정의된 기저 사례를 바탕으로 dp 배열을 채우는 역할을 한다.
먼저, N이 홀수인 경우에는 가능한 배치가 없으므로 0을 출력하고 프로그램을 종료한다.
그 후, N이 짝수인 경우에 대해 다음과 같이 값을 계산한다.

기본적으로 N=2일 때 경우의 수는 3이므로 dp[2]는 3으로 설정한다.
이후, N이 4 이상인 경우, 이전의 dp 값을 이용하여 새로운 값을 갱신한다.
각 i에 대해, dp[i]는 dp[i-2]와 dp[2]를 곱한 값으로 기본적으로 설정된다.
또한, i-4, i-6 등 이전의 모든 짝수 크기 패턴을 고려하여 추가적인 배치를 반영한다.
이러한 방식으로 점화식을 적용하여 dp 배열을 채운 후, 최종적으로 dp[N] 값을 출력한다.

4. 프로그램 실행 (main 함수)

메인 함수에서는 먼저 Input 함수를 호출하여 입력을 처리하고, 이후 Game_Start 함수를 실행하여 결과를 도출한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int N;
vector<int> dp;

void Input() {
	cin >> N;
	dp.resize(N + 1);

}

void Game_Start() {
	dp[0] = 1;
	dp[1] = 0;
	dp[2] = 3;
	if (N % 2 == 1) {
		cout << 0;
		return;
	}

	for (int i = 4; i <= N; i+=2) {
		dp[i] = dp[i - 2] * dp[2];

		for (int k = i - 4; k >= 0; k-=2) {
			dp[i] += dp[k] * 2;
		}
	}

	cout << dp[N];
}

int main(void) {
	Input();
	Game_Start();
}