[백준/C++] 11726번 2xn 타일링

 

 

 

 

문제코드

#include <iostream>

using namespace std;

int dp[1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;

	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) 
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
	
	cout<<dp[n];
}

 

 

문제 풀이

• 규칙을 찾기 위해 n=1~n=5까지 직접 구해보았다.
• dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=8 ... 이므로 구하고 싶은 항의 전 두개의 항을 더하면 원하는 값을 얻을 수 있다.
• dp[1]과 dp[2]의 값은 10007보다 작으므로 굳이 나눔처리 하지 않아도 된다.

 

 

 

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

11726번: 2×n 타일링