문제 설명

백준 ( BOJ ) 11726번 2xn 타일링

문제 분류 : 다이나믹 프로그래밍(dp)

문제 링크 : https://www.acmicpc.net/problem/11726

풀이

이번문제는 dp 문제 입니다.

언뜻 보면 매우 복잡한 문제일 수도 있는데요

차근차근 생각해보면 간단합니다!

블럭들의 규칙만 찾아주면 되거든요.

블럭은 ㅣㅣ ㅡ,ㅡ 이런식으로 이루어져 있습니다.

한번에 블록은 한칸씩 늘어나고요.

그럼 블록이 한칸 늘어났을떄,

어떻게 해야 하는가에 대하여 생각 해 봅시다.

N번째 블록을 만드려면, 우선 N-1 번째 블록에서

딱 1만 큼 공간이 증가하였기에, N-1 번째 블록에 ㅣ 이거를 붙여주면 됩니다.

이거 외의 경우의 수는 없을까요?

= < 이블록이 있어요 가로2개

그럼 2칸짜린데 어떻게 해야 할까요?

2칸전꺼에서 = 이블록을 붙여주면 됩니다.

그럼 N 번째 블록의 갯수는?

네 N-1 + N-2 가 되네요

마치 피보나치 수열과 같은 점화식입니다.

코드도 매우 간단합니다.

다만 10007로 계속 나눠주면서 하지 않으면

에러가 날거에요

저도 첨엔 long long 으로 만들고, 마지막에 10007로 나누었지만

long long 으로도 감당이 안되니

매번 계산마다 10007로 나누어 주면 됩니다.

코드

#include <iostream>
#include <vector>

using namespace std;


int main() {

	int n; 
	cin >> n; 

	vector<int> dp;
	dp.push_back(1);
	dp.push_back(2);
	for (int i = 2; i < n; i++) {
		dp.push_back((dp[i - 1] + dp[i - 2])%10007);
	}
	cout << dp[n - 1] ;
	
	return 0;
}