https://www.acmicpc.net/problem/11726
문제
> 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
접근
DP를 사용해서 직사각형을 채우는 방법의 규칙을 찾아 크기가 커졌을 때의 경우의수를 구한다.
문제해결
> n에대해 1일 때 부터 가능한 경우를 모두 따져보았다.
1일 땐 2x1 짜리만 한개 올 수 있으므로 1가지, 2일 땐 1x2 2개, 2x1 2개 올 수 있으므로 2가지가 된다.
> 3일 땐 1x2 2개가 먼저오고 2x1이 붙고, 반대로 2x1에 1x2 두개가 붙고, 2x1 3개가 오는경우 해서 3가지이다.
4, 5도 이처럼 그림과 같다. 그래서 각가 5, 8가지이다.
> n에 따른 경우의 수를 분석해보면 1,2 일 때 제외하곤 각각 직전의 경우와 그 전의 경우의 합이다. 즉 식으로 쓰면 n = n-2 + n-1이 된다. 따라서 이 식을 적용해 dp[n]값을 구해준다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int> dp(n+1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
cout << dp[n] << '\n';
}
후기
규칙을 다 구하고 제출했는데 틀려서 식에 뭔가 예외가 있나 계속 그렸는데 문제가 없었다. 알고보니 문제에 10007로 나눈값을 출력하고 되어있었다.
