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

문제

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.
[1, 1, 2, 3, 5, 8, .]
지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

제한 사항

• N은 1 이상 80 이하인 자연수이다.

입출력 

Nreturn

5	26
6	42

출처

 

분석

타일의 패턴 분석

타일은 앵무조개 나선형으로 큰 타일을 붙인다고 했습니다.

그렇다면 일단 문제를 풀기 전에 패턴을 봅니다.

 

타일을 가운데서 부터 나선형으로 된걸 나열하면

1, 1, 2, 3, 5 8 순서인데

분석해보면 피보나치 수열인걸 알수 있습니다.

 

** 그래서 피보나치 수열을 찾는 함수를 만들어야합니다. 

 

타일 둘레 길이 계산

N 번째 의 타일을 기준으로 지금까지 붙은 타일들의 둘레를 계산해야 합니다.

둘레 계산: 가로 + 세로 *2

 

N = 1 일때

(1 + 1) * 2 = 4;

 

N = 2 일때

(2 + 1) * 2 = 6;

 

하지만 이대로 구현 하기에는 맞지 않습니다. 타일이 쪼개져 있기 때문에

위 공식을 기준으로 좀더 개선해보면 아래 공식을 구할수 있습니다.

 

1. 현재 타일값 + 이전타일값 = 한변의 길이가 됩니다.

2. 현재 타일값 = 다른 변의 길이.

 

여기서 어떤게 가로 길이인지 세로길이 인지 구별할 필요가 없기 때문에

각각의 변의 길이를 구해줍니다. 

 

(현재 타일 값 + 이전 타일값 + 현재 타일값) * 2 = 둘레

(현재 타일값 *2 + 이전타일값) * 2 = 둘레 

 

구현

#include <string>
#include <vector>
#include<iostream>
using namespace std;



//피보나치 동적 알고리즘을 위한 memo
long long memo[9999999] ={0,1,1};


//이전 값을 저장하기 위한 변수
long long pre;

//피보나치 구현
long long fibo(int num){
   if( memo[num] ) return memo[num];

    //타일이의 이전값을 구하기 위해 이전값 저장
    pre = fibo(num - 1);
    long long next = fibo( num -2 );
    return memo[num] = pre + next;
}



//풀이 함수 구현
long long solution(int N) {
    long long answer = 0;

    //피보나치 함수를 이용하여 N 번째값 찾기
    long long cur = fibo( N ); 
    if( N == 0){
        answer = 2;
    } else {

       //(현재값 * 2 + 이전타일값)*2 = 둘레
        answer = (cur*2+pre)*2;
    }
    return answer;
}