[BOJ] 11726 2xn 타일링

🙂 문제 분석 및 프로그램 설계

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하는 것이다. n의 크기를 입력받고 경우의 수를 구한후 10007으로 나눈 나머지를 출력하면 된다.

⭐ 문제를 해결하는데 필요한 개념

다이나믹 프로그래밍(dp)가 무엇인지 알 수 있는 문제이다. 마치 수열의 점화식을 구하듯 찾아서 간단화하고 그것을 코드로 풀어서 내면 된다.

🗒️ 소스코드

#include <iostream>
#include <array>

using namespace std;

int main() {
	array<long long, 1001>arr;
	arr[0] = 1;
	arr[1] = 2;

	for (int i = 2; i < 1001; i++) {
		arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
	}

	int N;
	cin >> N;
	N--;
	cout << arr[N];

	return 0;
} 

😊 문제를 풀기 위해 생각하고 해결했던 과정 및 느낀점

경우의 수를 생각해 보다가 마지막 제일 오른쪽에 놓을 수 있는 경우가 위 그림처럼 2가지라는 것을 알 수 있었다. 첫번째처럼 하면 남은 공간은 2 x (n-1) 공간을 채울 수 있는 경우의 수가 있을 것이고 두번째처럼 하면 남은 공간은 2 x (n-2) 공간을 채울 수 있는 경우의 수이다.
즉 점화식이 an = a(n-1) + a_(n-2) 이렇게 나오고 그것을 코드로 풀어서 작성했다.

중간에 조건에 10007로 나눈 나머지 출력인데 이거 때문에 몇번 틀렸다.. 조건을 잘보자..
코드에는 long long으로 하였는데 int로 해도 잘 돌아갈 것 같다. 나는 코드가 커도 딱히 문제는 없으니 맘편하게 long long으로 작성하긴 했다.