(프로그래머스 c++)타일 장식물

문제를 잘 읽다보면 타일의 한 변의 길이가 피보나치와 같이 증가하는 것을 알 수 있다.

그래서 피보나치를 이용하여 N개의 타일의 한 변의 길이를 구하였다.

DP를 이용하여 arr[i] = arr[i - 1] + arr[i - 2] 의 값을 넣어주었다.

 

그리고 둘레의 길이를 구하는데 arr[N]의 길이와 arr[N - 1]의 길이가 필요하다는 것을 알 수 있다.

arr[N] * 4와 arr[N - 1] * 2를 더하여서 answer에 넣어주고 리턴하면 끝..!

 

주의점은 리턴값이 long long이므로 배열도 long long으로 해줘야 한다.

만약 int형이라면 효율성 테스트에서 틀리게 된다...!

#include <string>
#include <vector>

using namespace std;

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