[프로그래머스]동적계획법(Dynamic Programming) : 타일 장식물 (level 3)(c++)

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

코딩테스트 연습 - 타일 장식물

 

방법 1: 피보나치(DP)

#include <string>
#include <vector>

using namespace std;

long long solution(int N) {

    /*
        타일 한변의 길이는 피보나치 수열로 증가

        N번째 사각형이 더해진 전체 직사각형의 두 변 :
        - dp[N]
        - dp[N + 1] (= dp[N] + dp[N - 1])
    */
    vector<long long> tile(N + 2);
    
    tile[1] = tile[2] = 1;
    for (int i = 3; i <= N + 1; ++i)
    {
        tile[i] = tile[i - 1] + tile[i - 2];
    }

    return (tile[N] + tile[N + 1]) * 2;
}

 

 

방법 2: 피보나치 (두개의 변수만 활용)

using namespace std;

long long solution2(int N) {

    /*
        타일 한변의 길이는 피보나치 수열로 증가

        N번째 사각형이 더해진 전체 직사각형의 두 변 :
        - x : 이전의 y 값
        - y : x가 더해진 값
    */
    int x = 1, y = 1;
    for (int i = 0; i < N - 1; ++i)
    {
        int tmp = y;
        y += x;
        x = tmp;
    }

    return (x + y) * 2;
}

 

 

N번째 타일 한변의 길이를 DP[N]이라 하면,

피보나치 수열로 길이를 구한 후, (DP[N] + DP[N + 1]) * 2를 반환하는 문제였다.

 

마지막에는 결국 2변의 길이만 필요로 한다는 점을 생각해서

방법 2 처럼 x, y 두개의 변수만 가지고 값을 갱신해 나가도 된다.