[백준] 11726번 2Xn 타일링 (DP)

문제 링크입니다.

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

11726번: 2×n 타일링

1. 처음생각

- DP다. 점화식 찾아야한다.

- 1이랑 2는 맞고, 3부터는 이전꺼 두개 더한 값이다.

#include<iostream>
#include<vector>

using namespace std;

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

	return 0;
}

---

- 실패.. 엥 왜그러지;;

 

2. 두번째 생각

- 아..! 1을 넣으면 에러가 나네! 예외케이스때문에 그렇구만~! 처리해줘야지

#include<iostream>
#include<vector>

using namespace std;

int Solution(int n) {
	if (n == 1)return 1;	// 처리해줌
	vector<int> dp(n+1,0);
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}
int main() {
	int N;
	cin >> N;
	cout << Solution(N) % 10007;

	return 0;
}

---

- 실패.. 오잉..? 무슨문제지??

 

3. 세번째 생각

- 문제에서 10007으로 나눈 나머지를 출력하라 되어있고, 계속 숫자를 더하다보면 자료형의 크기를 넘을 수 있기에 연산할 때마다 10007로 나눈 나머지를 저장하여야 백준에서 제출할 때 런타임 에러를 방지할 수 있습니다.

- 오케 이거구나. 나머지를 출력하니까 처음부터 나머지가 들어가도 되는구나!

 

#include<iostream>
#include<vector>

using namespace std;

int Solution(int n) {
	if (n == 1)return 1;	// 처리해줌
	vector<int> dp(n+1,0);
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;	// 아예 넣을 때 나머지를 넣어주자..!
	}
	return dp[n];
}
int main() {
	int N;
	cin >> N;
	cout << Solution(N);

	return 0;
}

- 통과되었다.