[Lv 2] 2xn 타일링

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

프로그래머스

 

dp를 사용해 해결할 수 있다.

 

n = 1인 경우 타일 수는 1개이고

n = 2인 경우는 2개

n = 3인 경우는 3개이다.

마지막으로 n = 4인 경우는 5개이다.

 

따라서 점화식은 다음과 같다.

Dp[n] = Dp[n - 1] + Dp[n - 2]

 

이때 경우에 수에 1000000007을 나눈 나머지를 저장해야하기 때문에 dp의 값은 이 값을 나눈 나머지를 저장한다.

#include <string>
#include <vector>

using namespace std;
long long dp[60001] = {0,};
int solution(int n) {
    int answer = 0;
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3;i<=n;i++){
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
    }
    answer = dp[n];
    return answer;
}