개요

[링크]백준 11726번: 2xn 타일링

• 입력
  첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

• 출력
  첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

접근 방식

2xn의 타일을 채우는 경우의수를 F(n)이라 하자.
마지막 부분을 채울수있는 경우의 수는 1x2짜리 상자 하나채우는 경우인 F(n-1)과
2x1두개로 채우는 경우 F(n-2)로 나눌 수 있으므로

점화식을 세우면 F(n)=F(n-1)+F(n-2)가 된다.
이 식은 곧 피보나치 수열 식이다!

코드

#include<iostream>

using namespace std;
int dp[1001];
const int devideBy = 10'007;
void input(int& amount) {
	cin >> amount;
	dp[1] = 1;
	dp[2] = 2;
}
//2xn을 채우는 경우의수 F(n)이라하면 마지막 부분을 채울수있는 경우의 수는 1x2 하나채우는 경우인 F(n-1), 2x1두개로  채우는 경우 F(n-2)
//즉, 피보나치 수열이다.
void solution(int amount) {				
	for (int i = 3; i <= amount; i++)
		dp[i] = (dp[i - 1]%devideBy + dp[i - 2]%devideBy)%devideBy;
	cout << dp[amount];
}

int main() {
	int amount = 0;
	input(amount);
	solution(amount);

}

문풀후생

이런 류의 문제는 맨 뒤에서 어떻게 채울 수 있을까를 고민하면
점화식이 좀 잘 세워지는 걸 깨달았다.