[백준][11726번] 2×n 타일링

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

11726번: 2×n 타일링

 

풀이과정

 

1. dp로 접근했다.

 

2. dp[1] = 1, dp[2] = 2로 초기화 후 풀었다.

 

3. dp[N] = dp[n-1] + dp[n-2] 의 점화식을 구해야 한다.

- 2xN 크기의 직사각형의 경우 마지막에 채워 질 경우가 1x2라면 직전에 올 수 있는 경우의 수는 N - 2의 값이며

마지막이 2x1로 채워질 경우 N-1의 경우의 수를 가진다.

 

 

dp는 참 어렵다...

 

소스코드

#include<stdio.h>

int dp[1001];

int solution(int n) {

	if (dp[n] > 0) return dp[n];
	
	dp[n] = (solution(n-1) + solution(n - 2)) % 10007;

	return dp[n];
}

int main()
{
	int n;
	dp[1] = 1;
	dp[2] = 2;
	scanf("%d", &n);
	printf("%d\n", solution(n));
}