[프로그래머스] Level 2. 2 x n 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

 

해결방법

동적계획법으로 푼다. N길이의 타일을 길이가 1인타일과 길이가 2인 타일을 적절히 조합하여 놓는 경우의 수를 구하는 문제이다.  N길이의 타일을 까는 방법은 2가지가 있다. 

• N-1 길이까지 타일을 깐다음 세로타일깔기.
• N-2 길이까지 타일을 깐다음 가로타일깔기. 

따라서 f(n) = f(n-1) + f(n-2) 라는 결과가 나오게된다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
  
    if(n == 1) return 1;
    if(n == 2 ) return 2;
    
    int a = 1;
    int b = 2;
    
    for(int i= 3; i<=n; i++){
        int val = (a+b)%1000000007;
        a= b;
        b = val;
    }
    
    return b;
}

 

아~ 동적계획법 정말 생각해내기 힘들어. ㅠㅠ