[백준] 11726번: 2×n 타일링 / C++ / DP

풀이 문제 : 백준 11726번 2×n 타일링
풀이 언어 : C++
알고리즘 : 다이나믹 프로그래밍 
문제링크 : https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

문제요약

---

문제는 매우 간단하다.

 

접근 방식

---

처음엔 짝수랑 홀수를 따로따로 생각해봤는데 아무리 해도 답이 안나와서 알고리즘 분류를 봤더니 다이나믹 프로그래밍 문제였다,,
다이나믹 프로그래밍은 문제를 보자마자 알고리즘이 떠오르지 않아 어려운거 같다.

DP문제인 것을 깨닫고 나서 처음엔 재귀함수를 짜서 풀었다.

#include <iostream>
using namespace std;

int dp(int an) {
	if (an == 1) return 1;
	if (an == 2) return 2;
	return dp(an - 1) + dp(an - 2);
}

int main() {
	int n;
	cin >> n;
    
	//10007로 나눈 나머지 값 출력
	cout << dp(n) % 10007;

	return 0;
}

그러나 여기서 문제는 이미 한번 찾은 적 있는 값을 기억하지 못하고 계속 찾아야하기 때문에 값이 커질 수록 매우 비효율적이라는 것이다.

그래서 한번 찾으면 기억할 수 있는 코드를 다시 짜야겠다고 생각했다. (이게 진정한 DP를 푸는 방법이다)
이번엔 dp 배열을 만들어서 초기 값을 넣어주고, 작은 값부터 구하여 찾고자 하는 값까지 구하는 방식으로 코드를 짰다.

 

코드

---

#include <iostream>
using namespace std;

int dp[1001];

int main() {
	int n;
	cin >> n;

	dp[1] = 1;
	dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10007; //10007로 나눈 나머지 값 출력
	}
	
	cout << dp[n];

	return 0;
}

나머지 값을 한번에 계산하면 stack overflow가 발생할 수 있기 때문에 그때그때 계산해주어야 한다.

 

 

회고

---

1. DP 문제는 알아보기 힘들기 때문에 자주 풀어봐야 한다.
2. 나머지 값으로 결과를 출력하라는 문제는 stack overflow의 가능성을 확인해보고, 그때마다 계산해줘야하는 문제인지 판단해야 한다.