백준 11726번 : 2×n 타일링

링크 : https://www.acmicpc.net/problem/11726

문제읽기

단순하다. 2×n 크기의 직사각형이 존재하고 이를 1×2 또는 2×1 타일로 채워야 한다.

다이나믹 프로그래밍으로 잡혀있고 brute-force로 잡힌 것이 아닌 것으로 보아 단순한 알고리즘으로 풀리겠다는 것을 확인하자.

코드

#include<iostream>
using namespace std;

int dp[1000];

int main() {

	int n;
	cin >> n;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = ((dp[i - 1] + dp[i - 2]) % 10007);
	}
	cout << dp[n];
	return 0;
}

분석

바보여도 이런 바보가 없다. 다 분석해놓고 앞에서 헤렸다.

확인해보자. 계산하는 함수가 $f()$라고 하면

f(1) = 1
f(2) = 2
f(3) = 3 (==1+2)
f(4) = 5 (==2+3)
f(5) = 8 (==3+5)
...
f(9) = 55 (==21+34)

사실 55를 봤을 때 느낄 수 있었다. 55는 특별한 숫자니까 최소한 내가 아는 조합으로 숫자가 나온다는 것을 빨리 파악했어야 했다.

이렇게 식을 분석하면 점화식을 다음과 같이 얻을 수 있다.
$dp[n] = dp[n-1] + dp[n-2]$

따라서 base case가 되는 $dp[0]$과 $dp[1]$만 따로 처리해주면 되는 것이다.

문제의 특이점을 다음과 같이 확인할 수 있는데

이렇게 마지막에 10007로 나눠야 한다는 것이다. 이것은 찾아보니 계속 숫자를 더하다보면 자료형의 크기를 넘을 수 있기 때문에 백준에서 제출할 때 런타임 에러를 방지하기 위함이라고 한다. 호옹.

확실히 실버3 문제라 그런지 쉬운 것 같으면서도 어렵다. 하지만 깔끔하다. 내 패배다ㅠ