[프로그래머스] 타일 장식물

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

N개의 타일로 구성된 직사각형의 둘레를 구하기에 앞서, 각 타일들의 길이가 어떻게 되는지를 먼저 살펴봐야한다.
타일의 한 변의 길이는 1, 1, 2, 3, 5, 8, ... 이런 식으로 변한다. 그림을 잘 살펴보면 결국 한 변의 길이는 피보나치 수열과 일치함을 알 수 있다.
한 변의 길이를 피보나치 수열로 구할 수 있다는 것을 알게 되었으므로 이제 N개의 타일로 구성된 직사각형의 둘레를 구해보자.

위의 두 그림에서 빨간색 선의 길이는 동일하다는 것을 알 수 있다. 따라서 N개의 타일로 구성된 직사각형의 둘레는 N번째 사각형의 한 변의 길이를 fib[N]이라고 했을 때 4 * fib[N] + 2 * fib[N-1]이 된다.

코드

#include <string>
#include <vector>

using namespace std;

long long fib[81];

long long solution(int N) {
    long long answer = 0;
    fib[1] = 1;
    fib[2] = 1;
    // 한 변의 길이 계산
    for(int i=3; i<=N; i++)
        fib[i] = fib[i-1] + fib[i-2];
    if(N == 1) answer = 4;
    else answer = 4 * fib[N] + 2 * fib[N-1];
    return answer;
}