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

서론

피보나치수열과 DP문제.

프로그래머스의 레벨3 문제들만 풀고있는데, 같은 레벨인 문제들도 난이도 격차가 꽤 큰거같다. 이 문제는 DP의 전형적인 문제다.

풀이

그림이 그려져있다. 1, 1, 2, 3, 5, 8.... 피보나치수열이다. 그럼 DP를 이용한다.

문제를 보니 둘레를 구해야하는데

answer = (dp[N-1] + dp[N-2] + dp[N-2] + dp[N-3])*2;

위와 같이 점화식을 만들 수 있다.

그리고 N이 1, 2일때는 dp배열의 음수인덱스를 가지기 때문에 예외처리해줘야하는데,

예외처리를 해주지 않아도 통과한다. 테스트케이스가 없나보다.

구현

// c++

#include <string>
#include <vector>

using namespace std;

long long dp[81];

long long solution(int N) {
    long long answer = 0;
    
    dp[0] = 1;
    dp[1] = 1;
    
    for(int i=2; i<=N; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    answer = (dp[N-1] + dp[N-2] + dp[N-2] + dp[N-3])*2;
    
    return answer;
}