알고리즘(C++) / 프로그래머스 level 3 : 2 x n 타일링

level 3 : 2 x n 타일링

https://programmers.co.kr/learn/courses/30/lessons/12900?language=cpp 

코딩테스트 연습 - 2 x n 타일링

 

코드

//프로그래머스 2xn 타일링
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int dp[600001];

int DP(int num) {
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= num; i++)
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
    return dp[num];
}

int solution(int n) {
    int answer = 0;

    answer = DP(n);

    return answer;
}

int main() {
    int n = 4;
    cout << solution(n) << "\n";
    return 0;
}

 

설명

피보나치 수열과 같은 패턴을 가지고 있다. 피보나치 수열은 DP(동적계획법)로 풀 수 있다.

 

고찰

걸린시간 : 30분