백준, boj) 11726. 2xn 타일링(C / C++)

1. 문제 링크

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

11726번: 2×n 타일링

2. 문제 개요

2xn 크기의 직사각형을 1x2, 2x1타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

bottom up 방식으로 진행한다. 처음부터 쌓아 올릴 건데 어떤 데이터가 시작이 되어야 할까 잘 생각해보자.

 

4. 문제 풀기

dp[i]를 i번째 열에서의 최대 방법의 수라고 하자.

 

그럼 1칸을 전진하고자 하면, 세로로 길쭉한 벽돌을 쌓으면 된다. 그렇다면 i번째 칸을 쌓을 때는 i-1번째 칸에서 세로로 길쭉한 벽돌 1개를 놓는 경우가 있을 것이고,

i-2칸에서 가로로 길쭉한 벽돌 2개를 놓아서 i번째 칸에 도달하는 경우도 있을 것이다.

 

따라서

dp [i] = dp [i-1] + dp [i-2]라는 값을 얻을 수 있다.

사용된 벽돌의 개수를 묻는 문제가 아니다. 그냥 경우의 수만 더하면 되므로 위의 식처럼 구현하자.

 

5. 코드

#include <cstdio>
using namespace std;

int n;
int dp[1001]; // [index]번째 칸까지의 채우는 방법의 수

int main()
{
	scanf("%d", &n);

	//init value
	dp[0] = 0;
	dp[1] = 1;	//2x1 타일 1개를 세우는 방법이다.
	dp[2] = 2;	//2x1 타일 2개, 1x2타일 2개 총 2가지.

	for (int i = 3; i <= n; ++i)
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
		
	printf("%d", dp[n]);


	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~