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

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

 

서론

DP문제.

 

---

풀이

문제에 1000000007로 나눈 나머지를 출력하라는 조건이 있다. DP문제일 가능성이 매우 높으므로 규칙성을 찾는다.

 

직접 그려보니 result[n] = result[n-1] + result[n-2]인것 같다.

간단한 코드니 DP로 구현해본다.

통과.

 

---

구현

// c++

#include <vector>

using namespace std;

int dp[60001];

int solution(int n) {
    int answer = 0;
    
    dp[0] = 1;
    dp[1] = 2;
    
    for(int i=2; i<=n; i++) dp[i] = (dp[i-1] + dp[i-2])%1000000007;
    
    answer = dp[n-1];
    
    return answer;
}