[백준/C++]2133번 - 타일 채우기

백준 2133번 타일 채우기 문제 풀이: 동적 프로그래밍을 이용해 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 방법의 수를 찾는 법을 상세하게 설명합니다. 문제의 출처와 풀이, 그리고 코드까지 단계별로 알려드립니다. 동적 프로그래밍에 대한 실력 향상에 도움이 될 것입니다.

1. 문제출처: https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

2. 문제풀이

다이나믹 프로그래밍(DP)로도 풀 수 있습니다.

 

int n;
cin >> n;
dp[0] = 1;
dp[1] = 0;
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[i] + dp[j] * 2;
    }
}
cout << dp[n];

 

이 코드는 백준 2133번 '타일 채우기' 문제의 해결 코드입니다. 주어진 벽을 타일로 채우는 방법의 수를 계산하는 동적 프로그래밍 알고리즘을 구현한 것입니다.

1. int n; cin >> n; : 사용자로부터 벽의 크기(`n`)를 입력받습니다.

2. dp[0] = 1; dp[1] = 0; dp[2] = 3; : 초기값을 설정합니다. 가로 길이가 0인 벽을 채우는 방법은 빈 상태 하나이므로 1가지, 가로 길이가 1인 벽은 타일로 채울 수 없으므로 0가지, 가로 길이가 2인 벽을 채우는 방법은 세 가지입니다.

3. 첫 번째 for문 for (int i = 4; i <= n; i += 2) { ... } : 이 for문에서는 각 짝수 길이(`i`)에 대해 해당 길이의 벽을 채울 수 있는 방법의 수를 계산합니다.

dp[i] = dp[i - 2] * dp[2]; : 기본적으로 이전에 계산한 (i-2)길이의 벽에 대한 결과에 '세 종류'의 타일 조합(즉, dp[2])를 붙여서 만들 수 있는 조합들입니다.

내부 for문 for (int j = i - 4; j >= 0; j -= 2) { ... } : 여기서 계산하는 것은 추가적으로 고려해야 할 특별한 경우들입니다. 이전에 이미 계산된 결과 중에서 특정 부분(j길이)에 대해 '두 종류'의 특별한 타일 조합(각각 두 개씩, 따라서 '*2')을 붙여서 만들 수 있는 조합들입니다.

따라서 최종적으로 dp[i] 값은 기본적인 경우와 추가적으로 고려해야 할 특별한 경우들을 모두 합친 결과가 됩니다.

4. 마지막으로 cout << dp[n]; 로 주어진 크기(`n`) 의 벽을 채울 수 있는 모든 가능한 방법의 수를 출력합니다.

따라서 이 코드 부분은 주어진 벽을 타일로 채울 수 있는 방법의 수를 계산하는 동적 프로그래밍 알고리즘을 구현한 것입니다.

3. 문제코드 

#include<iostream>
#include<algorithm>

using namespace std;

int dp[31];

int main() {
	int n;
	cin >> n;
	dp[0] = 1;
	dp[1] = 0;
	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[i] + dp[j] * 2;
		}
	}
	cout << dp[n];
}

 

이 글을 통해 백준 2133번 '타일 채우기' 문제에 대한 풀이 방법을 이해하셨기를 바랍니다. 동적 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 강력한 알고리즘입니다. 계속 연습하면서 이 알고리즘에 익숙해지시면, 더 어려운 문제도 해결할 수 있게 될 것입니다.