백준 11726번 2xn 타일링 [성공]

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

11726번: 2×n 타일링

다이나믹 프로그래밍으로 대표적인 문제

#include <iostream>
#include<vector>

using namespace std;

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

기본적으로 모든 다이나믹 프로그래밍이 그렇듯 점화식을 구한다면 쉬운문제

기준을 뒤에서 부터 쌓는다고 생각하면 쉽게 구분이 가능하다.

1X2블럭을 2개 쌓는 것과 2X1블럭을 하나 쌓는 것으로 두개를 구분한다.