[백준 - 11726] 2×n 타일링

#include <iostream>
using namespace std;

unsigned long long int DP[1001];

int main()
{
	//1. Get input
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;

	//2. Set initial value
	DP[1] = 1;
	DP[2] = 2;

	//3. Set All DP with loop
	for (int i = 3; i <= N; ++i)
	{
		//여기서 mod를 해야 양수에서 mod를 하게 된다.
		DP[i] = (DP[i - 1] + DP[i - 2]) % 10'007;
	}

	//4. Print
	cout << DP[N];
	return 0;
}

---

||사고 과정

2 x 1일때 부터 2 x 4까지 직접 노가다로 하면서

이전의 타일의 결과 값을 이용할 수 있지 않을까 해서 DP라는 느낌이 강하게 왔다.

 

그렇게 규칙을 찾긴했는데 뭔가 DP로 푸는 이유가 어정쩡해서 다른 사람들은 왜 DP로 생각했는지 보았는데

백준 11726번: 2xn 타일링

이분글이 제일 이해가기 쉬웠다.

명확한 이유 ㄷㄷ

---

||사용 기법

• DP

---

||새로 알게 된것

• overflow

이 문제에는 답을 10,007로 나눈 나머지를 출력하라고 나와있어서

나는 Loop을 끝내고 나서 Printf를 했는데 자꾸 오류가 나더라 =~=

알고보니 int형의 overflow때문..

 

loop때 구해지는 DP의 값이 overflow라면 DP에 들어갈때 DP의 자료형만큼 로 값이 잘리고 다시 더해서 들어가는데

값을 넣기전에 나누고 나머지를 저장하는 식으로 회피했어야 했다.

 

다시 한번 잘 알게 됐다!