BaekJoon 11726번: 2xn 타일링

풀이법

1) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다.

    방법만 안다면 쉽게 풀 수 있는 문제이나 정답률이 낮은 이유는 여러 번 시도한 사람이 많아서일 것이다.

    1차원 배열을 선언 한 후 규칙을 찾아 보았다.

 

   

 

    n=1 : 1개

    n=2 : 2개

    n=3 : 3개

    n=4 : 5개

 

위의 요소를 토대로 규칙을 찾아보니 일종의 계차수열임을 알 수 있었다.

점화식을 구해보니 arr[i]=arr[i-1]+arr[i-2]를 도출할 수 있었다.

10007로 나눈 나머지를 구해야 하므로 최종 점화식은

arr[i] = arr[i-1]%10007 + arr[i-2]%10007 이 된다.

최총 출력 값: arr[n]%10007

 

#include <iostream>
#include <algorithm>
using namespace std;

int fix = 10007;
int n;
int arr[1001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	arr[1] = 1;
	arr[2] = 2;
	for (int i = 3; i <= n; i++)
	{
		arr[i] = arr[i - 1]%fix + arr[i - 2]%fix;
	}
	cout << arr[n] % fix;
}

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest