[백준] 11727번 2Xn 타일링 2 (DP)

문제 링크입니다.

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

11727번: 2×n 타일링 2

1. 첫번째 생각

- dp는 이전꺼 활용하는거다.. 어떻게 활용해볼까? 

- 손으로 먼저 풀어보는거 중요한거 같다. 

- n칸을 어떻게 채워야할까? = 한칸 비었을때 다 채우려면 어떻게 채워야할까? + 두칸 비었을 때 다 채우려면 어떤 방식으로 채워야할까?

- dp[n] = dp[n-1] + 2*dp[n-2]

- 한칸 비워져있을 때는 이전꺼 그냥 넣으면 된다.

- 두칸 비워져 있을 때는 2*1 짜리 두개랑, 2*2 짜리 하나 넣는 두가지 방법 존재. 그래서 두배해줌.

- 8개까지 돌려보니까 171 나와서 그냥 바로 돌려보았다.

#include<iostream>
#include<vector>

using namespace std;

int Solution(int n) {
	if (n == 1)return 1;	// 처리해줌
	vector<int> dp(n+1,0);
	dp[1] = 1;
	dp[2] = 3;
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + 2*dp[i - 2]) % 10007;	// 아예 넣을 때 나머지를 넣어주자..!
	}
	return dp[n];
}
int main() {
	int N;
	cin >> N;
	cout << Solution(N);

	return 0;
}

- 통과되었다.