[프로그래머스] DP(2) 타일 장식물

문제 설명

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

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

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

제한 사항

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

 

입출력 예

N	return
5	26
6	42

 

풀이

#include <iostream>

using namespace std;

long fibo_list[80]; // 피보나치 수열 list
long last; // 마지막 피보나치 수

int fibo(int n) {
    fibo_list[0] = 1;
    fibo_list[1] = 1;
    
    // 피보나치 반복 알고리즘
    for (int i = 2; i < n; i++) {
        fibo_list[i] = fibo_list[i-1] + fibo_list[i-2];
    } 
 
    last = fibo_list[n-1];
    
    return fibo_list[n];
}

long long solution(int N) {
    long long answer = 0;
    int x;
    
    x = fibo(N+2); // 반복 알고리즘이 2부터 돌기 때문에 N+2 해준다.    
    answer = (x + last)*2 + x*2; // 둘레 계산
        
    return answer;
}

 

숫자의 반복이 피보나치 수열임을 파악하고,

피보나치 풀이인 재귀, DP, 반복 중 반복을 택하였다.

 

피보나치 풀이에 대해서는 다음 게시물을 참고하자!

https://seoyeonkk.tistory.com/12

 

이후, 사각형의 둘레는 계산하는 방법을 고민하였다. 

둘레를 구하는 방법은 다음과 같다.

피보나치 f(N)이 width(or height)라면, f(N)+f(N-1)이 height(or width)가 된다.

직전의 피보나치 수열 수를 last에 저장하여 둘레를 계산하도록 하였다.

 

처음 fibo(N)했을 때, 전전의 값이 나와 당황스러웠다.

fibo알고리즘에서 for문을 돌릴 때 i번째까지 저장하기 때문이다.

따라서, fibo(N+2)를 하였을 때 제대로 된 값을 얻을 수 있다.

 

정확성, 효율성 테스트 다 맞았다.

해당 문제 링크

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

코딩테스트 연습 - 타일 장식물 | 프로그래머스