정답률을 보고 만만하게 봤다가 혼난 문제…

문제

  • 2xn일 때 2x1, 1x2, 2x2크기의 타일로 해당 공간을 채우는 방법을 제시하면 된다.

입력

  • 첫째 줄에 정수 n이 주어진다.

출력

예제 입력
2
예제 출력
3
예제 입력
8
예제 출력
171
예제 입력
12
예제 출력
2731

접근

  • 다이나믹 프로그래밍을 어떻게 사용할까?

내가 생각한 풀이

  • 부끄러운 첫번째 생각 : 아 딱보니깐 규칙이 있겠네!! -> 한참동안 털리고 정신 차렸음.
  • 다이나믹 프로그래밍으로 접근한 새로운 생각 앞에서 구한 n에 대응하는 값들을 뒤에서 재사용하자!
    • 구해놓은 타일을 그대로 가져다 놓은 다음 뒤에 코일들을 더 붙이는 것을 생각!
  • 맨 마지막에 올 수 있는 타일은 2x2, 2x1, 1x2가 있다.
  • 따라서 n-2개 2개(1x2나 2x2는 뒤에 두칸을 써야하므로), n-1개 1개를 더해주면 n번째 타일의 경우의 수가 될 것이다.

코드

#include<iostream>
using namespace std;
int main(void){
  int c, d[1002];
  cin>>c;
  d[1] = 1; d[2] = 3;
  for(int i = 3 ;i<=c;i++){
    d[i] = (d[i-1] + d[i-2]*2)%10007;
  }
  cout<<d[c];
  return 0;
}