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

동적프로그래밍 카테고리로 분류된 문제였지만,

피보나치를 활용해도 풀리고 어렵지 않은 문제였습니다.

---

문제보기

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

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

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

제한 사항

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

입출력 예

N	return
5	26
6	42

---

내 풀이

타일을 이어 붙이면서 늘어나는 변의 길이를 나열해보면 아래와 같다.

(각각 1,2,3,4..N번째 타일이라고 표현하겠음)

1, 2, 3, 5, 8, 13, ...

 

그리고 1, 2, 3, ..., N개의 타일로 구성된 직사각형의 둘레를 나열해보면 아래와 같다.

4, 6, 10, 16, 26, 42, ...

 

이렇게 쭉 적고나면 가장 먼저 변의길이에서 규칙을 찾을 수 있다.

타일 변의 길이들은 피보나치 수열의 형태를 띄고 있다.

 

또한 문제의 그림에서 볼 수 있듯이 타일의 둘레는 아래와 같다.

 

타일의 둘레 = (작은 변의 길이 * 2) + (긴 변의 길이 * 2)

                = (작은 변 길이 + 긴 변 길이) * 2

 

여기서 작은 변의 길이는 N-1번째 타일 변의 길이 이고 긴 변은 N번째 타일 변의 길이이다.

 

그대로 코드로 구현했다. 쉬운문제였다.

class Solution {
    public long solution(int N) {
        long[] width = new long[N];
        width[0] = 1;
        width[1] = 2;
        for(int i=2; i<width.length; i++){
            width[i] = width[i-1]+width[i-2];
        }
        return (width[N-2]+width[N-1])*2;
    }
}

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/43104?language=java

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