BOJ) 11726 2xn 타일링 <C++>

백준 11726 2xn 타일링 <C++>

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

이번 문제를 보고 가장 먼저 든 생각은

"입체적으로 생각할 필요 없이 주어진 가로 길이를 1과 2의 선분을 활용해서 만들어봐라"였다.

 

앞서 여러 DP문제들을 풀어보면서 DP문제들은 그림으로 풀어보는 것이 가장 좋다고 생각해서

차근차근 경우를 그려가며 생각 해보았다.

 

 

로직

규칙을 찾으면서 그려보았고 해당 그림에서 규칙이 보였다.

가로가 n 일때에는 n - 1 과 n - 2에서 가능한 경우를 더하면 되는 것이였다.

 

따라서 

• 가능한 경우의 수[n] = 가능한 경우의 수[n - 1] + 가능한 경우의 수[n - 2]

 

가 되는 것이였다.

그리고 이번 문제의 함정이 있었는데 바로 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력해야 하는 것이였다.

따라서 항상 값을 구할때 마다 10007로 나눈 나머지를 저장해 주었다. 

카테고리

• DP(Dynamic Programing)

코드

#include <iostream>
#include <vector>

std::vector<int> dp_vector;
int n;

void output()
{
	std::cout << dp_vector[n];
}

void solution()
{
	dp_vector[1] = 1;
	dp_vector[2] = 2;
	for (int i = 3 ; i <= n ; i++)
	{
		dp_vector[i] = dp_vector[i - 2] + dp_vector[i - 1];
		if (dp_vector[i] >= 10007)
			dp_vector[i] %= 10007;
	}
}

void input()
{
	std::cin >> n;
	dp_vector.resize(n + 1);

}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input();
	solution();
	output();
}