백준 11726 [C++]

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

1. 풀이방법

- 이 문제를 접할 때 점화식을 생각해내는 게 생각보다 어려웠습니다.

 

- 물론 이런 류의 문제는 알고나면 매우 간단하기는 하지만......!

 

- 결국 점화식은 dp[n]=dp[n-1] + dp[n-2] 입니다 

 

- 그림을 보시면 이해가 쉬우실 듯 합니다.

 

 

2. 주의사항

 

- 값을 저장할 테이블을 구성해서 메모이제이션을 활용하여 시간을 단축시켜주었습니다.

 

- 탑다운 방식으로 재귀함수만을 이용하여 연산하는 경우 중복되는 연산을 너무나 많이 하기때문에

 

- TIME LIMIT을 만나실 수 있습니다.

 

- 저장되어있는값이 있으면 바로 리턴해서 가져다 쓰고 새로운 값이면 테이블에 저장을 한 후 리턴해서

 

- 다음부터는 그 값이 필요할 때 테이블에서 바로 가져다 쓸 수 있도록 하면 됩니다.

 

 

 

 

 

3. 나의코드

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

int  n;
int dp[1001];

int getdpvalue(int num) {
	if (dp[num] == 0) { 
		dp[num] = (getdpvalue(num - 1) % 10007 + getdpvalue(num - 2) % 10007);
		return dp[num] % 10007;
	}
	else return dp[num]%10007;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	dp[1] = 1; dp[2] = 2; dp[3] = 3; // 3을 초기화안해줘도 되긴하다
	                                 // (하지만 경우의수 그림 그려놨으니까..아까워서)
	cout<<getdpvalue(n)<<"\n";

	return 0;
}