문제풀이/백준
[C++] 백준 - 11727 : 2 x n 타일링 2
orubt
2020. 3. 14. 19:00
반응형
11727번: 2×n 타일링 2
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
www.acmicpc.net
풀이 ) DP
앞문 제인 2 x n 타일링과 다른 점은 시작하는 방법이 하나 추가됐다는 점이다.
2 x 1 타일로 시작할 수 있고 이 때는 뒤에 2 x (n-1) 직사각형을 채우면 되고
1 x 2 타일 2개로 시작하거나 2 x 2 타일로 시작하는 경우는 뒤에 2 x (n-2) 직사각형을 채우면 된다.
따라서 점화식은 memo[n] = memo[n-1] + 2 * memo[n-2]이다.
#include <cstdio>
#include <algorithm>
using namespace std;
int memo[1002] = {0, 1, 3, };
int main(void)
{
int n;
scanf("%d", &n);
for(int i = 3; i <= n; ++i)
memo[i] = (memo[i-1] + memo[i-2]*2)%10007;
printf("%d\n", memo[n]);
return 0;
}
주의점 )
앞 문제와 같이 모듈러 연산은 for문에서 한다.
반응형