[코딩테스트] 백준11727 2xn 타일링 2

📃2Xn 타일링 2 문제 바로가기

문제 풀이

• DP 를 이용하여 푸는 문제이다.
• Dynamic Programming 알고리즘은 memoization을 한다는 특성을 가지고 있는데, 이는 이전 결과값을 저장하여 다음 계산에 이용을 하는 방식이다.
• 본 문제의 경우, 2xn에서 이용한 타일의 개수를 구하고 싶다면, 2x1부터 시작하여 2xn까지 결과를 계산하면된다.
  - 홀수의 경우 2xn의 개수에서 -1을 해주어야하고,
  • 짝수의 경우 2xn의 개수에서 +1을 해주어야한다.
• 또, 이 값들을 그냥 저장하게 되는 경우 오버헤드가 발생한다. 따라서 문제에서 주어진 %100007을 미리 계산하여 저장한다면 이를 방지할 수 있다.

C++ 코드

#include<iostream>

#define NUMBER 1001
using namespace std;


int main() {

	int n; 
	cin >> n; 

	int memoization[NUMBER];
	memoization[1] = 1; 

	for (int i = 2; i <= n; i++) {
		if (i % 2 == 0) {//짝수인 경우
			memoization[i] = (memoization[i - 1] * 2 + 1)%10007;
		}
		else {
			//홀수 인 경우
			memoization[i] =(memoization[i - 1] * 2 - 1)%10007;
		}
	}



	printf("%d\n", memoization[n] );

	return 0;
}