[프로그래머스_레벨 3] 2 x n 타일링

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

코딩테스트 연습 - 2 x n 타일링 | 프로그래머스

백준에 동일한 문제가 있다.

이 문제는 dp로 풀 수 있는데 n=1, n=2, ...일 때를 해보면 경우의 수가 피보나치 수열을 이루고 있음을 알 수 있다.

이렇게 점화식이 간단히 나오는 경우 쉽게 풀 수 있지만 좀 더 어려운 dp문제는 점화식을 찾는데 주력해야 한다. 그 뒤에는 쉽게 dp문제를 풀 수 있다.

 

피보나치 수열은 dp[n] = dp[n-1] + dp[n-2] (n은 3이상 자연수) 의 점화식을 가지므로 그대로 구현해주면 된다.

유의할 점은 연산 후 mod로 나눈 나머지를 저장해줘야 한다는 것이다.

#include <string>
#include <vector>
#define mod 1000000007
 
using namespace std;
 
int dp[60001];
int solution(int n) {
    dp[1] = 1; dp[2] = 2;
    if(n <= 2) return dp[n];
    for(int i=3; i<=n; i++){
        dp[i] = dp[i-1] + dp[i-2];
        dp[i] %= mod;
    }
    return dp[n];
}