[프로그래머스] 2 x n 타일링 c++

문제 링크 

 

 

리뷰 

n이 1일때, n이 2일때 부터 n이 5일때 몇 가지 경우의 수가 있는지 그려보면 규칙성이 보인다. 

공간의 세로 길이는 항상 2다. 

모든 막대는 1 X 2크기다. 

n == 1 이라면,	공간은 2 X 1	막대 1개를 세우는 것 만 가능하다.	1가지 가능
n == 2	공간은 2 X 2	막대 2개를 세우거나, 둘 다 눞이면 된다.	2가지 가능
n == 3	공간은 2 X 3	막대 3개를 세우거나, 두개는 눞인다.	3가지 가능

아래는 n == 5 인 경우, 가능한 배열을 그린것이다. 

막대 5개를 세운다. 

막대 3개는 세우고, 2개는 눞인다. 

막대 1개는 세우고, 4개는 눞인다. 

맞았습니다 코드 

#include <string>
#include <vector>
#define MOD 1000000007
using namespace std;

int D[60001];
int solution(int n) {

  D[1] = 1, D[2] = 2; 
  
  for(int i = 3; i <= n; i++){
    D[i] = (D[i-1] + D[i-2] ) % MOD;
  }
  return D[n];
}