[BOJ] 11726 - 2xN 타일링 1
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력 1
2
예제 출력 1
2
예제 입력 2
9
예제 출력 2
55
DP 를 확실히 공부하고 나니 DP로 풀어야 겠다는 생각은 바로 들었다. 알듯 말 듯 답이 떠오르지 않아 수열을 계산해 봤는데 피보나치 수열이 나왔다. 일단 풀고 보자 싶어서 풀었다. 처음에는 10,007로 마지막에 모듈러 연산 하여 답을 출력했는데 틀렸다고 나왔다. 질문을 검색해보니 10,007 이라는 큰 소수로 나눔으로써 메모이제이션을 하면서 값이 제대로 저장되지 않음을 방지하는 것이라 연산하는 도중에 모듈러를 해줘야 했다. 그리고 손쉽게 문제를 해결했다.
코드
#include <iostream>
using namespace std;
int memo[100000]={0,};
int find(int n){
memo[1] = 1; memo[2] = 2;
if(n==1) return 1;
if(n==2) return 2;
for(int i=3;i<=n;i++){
memo[i] = (memo[i-2]+memo[i-1])%10007;
}
return memo[n];
}
int main(){
int n;
cin>>n;
cout<<find(n);
}
| cs |
답이 피보나치수열인 이유
N 열의 타일링을 채우는 경우의 수를 f(n)이라고 할 때, f(n)은 제일 오른쪽을 가로 블록 2개로 채운 경우의 수 + 세로 블록 1개로 채운 경우의 수이기 때문에 점화식은 결국
f(n) = f(n-1) + f(n-2) 가 나온다.
예를 들어, 만약 2*5칸짜리 타일이 있고 오른쪽을 가로 타일 2*1 2개로 채웠으면 결국 2*3 칸을 채우는 경우의 수가 답이 되고, 오른쪽을 2*1 1개로 채우면 2*4의 경우의 수가 나오므로 피보나치 수열이 점화식이 되는 것이다.
No comments: