[백준] 11726.cpp : 2 x n 타일링

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

#include <iostream>
#include <array>

using namespace std;

int n;
array<int, 1000> arr = {0,};

/*
int solve(int num, int idx)
{
  int res = 0;
  // 재귀로 푼 코드
  if(num == 0) return 1;
  // 현재 1x2 상자의 위치에서 가능한 다른 박스들을 탐색
  for(int i = idx ; i < n - 2* (num-1) - 1 ; i++)
  {
    res += solve(num - 1, i + 2);
  }

  return res;
}
*/

int main(void)
{
  cin >> n;
  int temp = n;
  int res = 0;
  // 피보나치와 같은 패턴
  arr[0] = 1;
  arr[1] = 2;
  for(int i = 2 ; i < n ; i++)
  {
    arr[i] = arr[i-1] + arr[i-2];
    // 그냥 넣을 경우 오버플로우가 바로 터져버린다. 매번 나머지 연산 해주기!
    arr[i] %= 10007;
  }
/*
  // 재귀 코드 호출부
  while(temp >= 0)
  {
    int t = solve((n -temp) / 2, 0);
    res += t;
    temp -= 2;
  }
*/
  cout << arr[n - 1] << '\n';
}

 

[Try]

1. 세로가 2줄로 고정되어있으니, 2x1 도형의 위치를 가능한 갯수별로 조합을 사용하여 구하면 될 것 같다.

     단순 조합의 갯수로는 안되는게, 1x2 도형이 2개칸을 차지하기 때문에 그걸 고려해줘야 한다. 재귀적으로 풀 수 있을 것 같다.

2. 재귀는 역시 시간초과가 뜬다. 다른 패턴을 잘 생각해 볼 것

3. 피보나치와 같은 패턴이기 때문에 값이 어마어마하게 커진다. 일반적인 int 자료형은 46번째에서 컷 당함

 

[Point]

1. 수학적으로 접근할 수 있는 사고력

 

[More]

1. 동적 계획법 / 다이나믹 프로그래밍