[백준] 2 x n 타일링

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

 

 

타일 채우기 문제. 타일 채우기 문제들은, DP를 연습할 때 가장 많이 접하는 유형이기도 하다.

 

---

1. 문제 분석

 

가. 문제 분류

 

타일의 채우는 전체의 경우의 수를 구해야하므로, 완전 탐색 문제.

최적화 문제는 아님. 단순히 전체 경우의 수를 구해 반환하면 됨.

 

 

나. 접근 아이디어

 

2 x n 크기의 직사각형을 채울 경우의 수는 다음과 같이 생각해 볼 수 있음.

2 x n 크기를 채울 경우의 수
= (세로 직사각형 하나 + 2 x n - 1 크기를 채울 경우의 수) + (가로 직사각형 두개 + 2 x n - 2 크기를 채울 경우의 수)

 

즉, 2 x n 크기를 채울 경우의 수를 리턴하는 함수를 fill(n)이라 했을 시, 

 

f(n) = f(n - 1) + f(n - 2)

가 성립한다는 것을 알 수 있음. 즉, 피보나치 수열과 동일한 문제임.

 

 

2. 완전 탐색으로 접근

 

수도 코드를 작성해 보면,

 

def fill(n):
	if n == 0 or n == 1: return 1;
    return fill(n - 1) + fill(n - 2)

 

간단 명료하게 작성해 볼 수 있음.

 

3. 메모이제이션으로 중복되는 부분의 연산을 줄일 수 있을까?

 

조합 문제, 피보나치 수열과 마찬가지로, 이 문제 또한 n이 커질수록 하위의 중복되는 fill함수 호출이 급격하게 커짐.

또한, 입력에 따라 결과 값이 하나로 정해지므로(참조적 투명 함수이므로), 메모이제이션 적용 가능.

 

 

4. DP적 접근

 

메모이제이션 구현 레시피를 적용하면(https://sanghoonly.tistory.com/29) 손쉽게 문제를 해결할 수 있음.

#include <iostream>
#include <memory.h>

using namespace std;

int cache[1001];

int fill(int n)
{
  if (n == 0 || n == 1)
    return 1;

  int &ret = cache[n];

  if (ret != -1)
    return ret;

  return ret = ((fill(n - 1) + fill(n - 2)) % 10007);
}

int main(void)
{
  int N;

  cin >> N;

  memset(cache, -1, sizeof(cache));

  cout << fill(N) << '\n';

  return 0;
}