백준 11726번 ( 2 x N 타일링 )

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

11726번: 2×n 타일링

DP를 이용해 풀어야 하는 문제이다.

DP를 사용하기 위한 조건
   1. 큰 문제를 작은 문제로 나눌 수 있다.
   2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

위 조건에 부합하기 때문에 DP를 사용한다.
DP는 규칙을 찾아서 점화식을 세우는 것이 가장 중요하기 때문에 우선 규칙을 생각한다.

n-1, n-2 까지는 채워진 경우의 수가 구해진 상태라고 가정하자. 그 후 맨 뒤에 길이를 추가하면 될 수 있는 경우의
수는 2가지이다.

위와 같이 타일의 세로 길이가 n일 때 타일을 채우는 경우는 "2x1" 타일을 쓰는 경우, "1x2" 타일을 쓰는 경우
두가지이다. 그렇기 때문에 점화식은 다음과 같다.

 

D[i] = D[i - 1] + D[i - 2]

 

틀린 코드 ( overflow 문제 발생 )

#include <stdio.h>
#include <iostream>

using namespace std;

int d[1001];

int tile(int n){
  if(n == 1) return 1;
  if(n == 2) return 2;
  if(d[n] != 0) return d[n];
  
  d[n] = tile(n-1) + tile(n-2);
  return d[n];
}

int main(){
  int n;
  scanf("%d",&n);
  printf("%d",tile(n) % 10007);
}

처음에 위와 같이 코드를 구현했더니 계속 틀렸습니다라고 나와서 당황스러웠다.
사실 틀렸습니다가 나온 이유는 재귀 호출해서 값을 계속 더하는 문제는 값이 매우 커지는 경우가 많기 때문에
OverFlow문제를 야기할 수가 있다.

=> 즉, 문제에서 10007로 나누라던 이유도 값이 매우 커져서 int값을 넘어가 overflow가 발생하는 경우를 방지하기
     위함이다. 그러므로 tile 함수 안에서 10007을 나눈 나머지를 배열에 저장하도록 구현해야 overflow가 나지 않고
     문제를 해결할 수 있다.