[DP] 백준 문제 풀이 - 11726 2xN 타일링

👩🏻‍💻 문제링크

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

11726번: 2×n 타일링

 

✍️ 아이디어

1. 문제 이해

• 문제를 해석하던 도중 단순화 해보니까 n을 1과 2의 합으로 나타낼수 있는 경우의 수였다
• 그리고 n을 1부터 6까지 나열하여 이게 피보나치 수열과 같은 형태라는것을 알게되었다

-> 하지만 이것이 왜 피보나치 수열과 같은 형태가 나오는지는 이해하지 못했다

 

2. 점화식 : 직접 써보면 나옴 = 피보나치 수열

 

✍️소스코드

•  (A + B) % M =  (A%M + B%M) % M 이거시 성립한다 -> 이거 안쓰면 오버플로우 생김

#include <iostream>	
using namespace std;
long long result[1001];

int main()
{
	int n; cin>>n;
	result[1]=1;
	result[2]=2;
	for(int i = 3; i<=n; i++)
	{
		result[i]=((result[i-1]%10007)+(result[i-2]%10007))%10007;
	}
	cout<<result[n]<<'\n';
}

 

✍️피드백

피보나치 수열과 같은 형태가 나오는 이유 :

가장 오른쪽에 타일을 놓는 경우의 수는 2가지가 있는데...각각의 경우의 수는 result(i-1)과 result(i-2)이다

체감난이도	걸린시간	참고	사용 문법
하	30min	백준 질문 코너	수학의 나눗셈 공식