728x90
반응형
https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
위 그림처럼 점화식은 dp(n) = dp(n-1) + 2 X dp(n-2)가 된다
#include <bits/stdc++.h>
using namespace std;
int n;
int dp[1001];
int main(void) {
cin >> n;
dp[1] = 1;
dp[2] = 3;
for(int i=3; i<n; i++){
dp[i] = (dp[i-1] + 2*dp[i-2])%10007;
}
cout << dp[n];
return 0;
}728x90
반응형
'알고리즘' 카테고리의 다른 글
| [백준/DP/C++] 10844번 쉬운 계단 수 (0) | 2022.12.24 |
|---|---|
| [백준/DP/C++] 9095번 1,2,3 더하기 (0) | 2022.12.23 |
| [백준/DP/C++] 11726번 2xn 타일링 (0) | 2022.12.19 |
| [이코테/DP/C++] 병사 배치하기 (최장 증가 부분 수열 알고리즘, LIS) (1) | 2022.12.14 |
| [이코테/DP/C++] 금광 (0) | 2022.12.13 |