[프로그래머스, 자바] 타일 장식물 - 동적계획법, 피보나치수열

프로그래머스 3단계 타일 장식물 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/43104?language=java

문제설명

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

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

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

제한사항

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

입출력 예

N	return
5	26

자바코드

            
class Solution {

    public long solution(int N) {
        long[] fibonacci = new long[N + 1];
        fibonacci[1] = 1;
        for (int i = 2; i < fibonacci.length; i++)
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];

        return round(N, fibonacci);
    }

    public long round(int N, long[] fibonacci) {
        return fibonacci[N] * 4 + fibonacci[N - 1] * 2;
    }

}

문제설명

이 문제는 특정한 규칙을 발견할 수 있는데, 바로 피보나치이다. 피보나치는 재귀를 통해서도 계산이 가능하고, 동적계획법을 이용해서도 풀이가 가능하다.

재귀를 사용하면 큰 수를 사용했을 때, 스택오버플로우가 발생할 수 있는 가능성이 존재하기 때문에 동적계획법을 이용해서 풀었다. 그리고 방식은 동일하다.

결국은 이전 값에 대해서 메모리제이션으로 기록을 하느냐 하지 않느냐의 차이이다. 타일의 길이를 보면 아래와 같다. 

 - 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ... --> 혹시나 하는 마음에 몇 개 더 계산해봤는데 맞았다. 운이 좋았다.

각각 타일의 길이를 알았다면, 이제는 전체 타일의 둘레를 구해야 할 것이다. 이럿도 N = 5, N = 4 일때를 한번 직접 손으로 적어봤는데,  일정한 규칙이 있었다.

 - N = 5 --> F(5) * 3 + F(4) * 2 + F(3) * 2 + F(2) * 2 + F(1) * 1 == F(5) * 4 + F(4) * 2

이 문제는 동적계획법을 이용한 문제라고 했지만, 어떻게 보면 규칙성을 발견하는 것이 더 중요한 문제라고 생각한다. 

운이 좋아 규칙을 쉽게 발견해서 쉽게 풀 수 있었다.

근데 브래드는 언제오나.. Pair Coding 해야하는데 ....