프로그래머스 LEVEL 3 : 타일 장식물

프로그래머스 LEVEL 3 : 타일 장식물

언어 : JAVA

---

문제

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

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

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

제한 사항

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

입출력 예

N	return
5	26
6	42

---

핵심

문제의 규칙을 이해하는 것이 중요하다.

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

• 규칙 1 : 위 수의 규칙을 보면 '피보나치 수' 임을 알 수 있다.
• 규칙 2 : 도형의 둘레는 (현재 도형 한 변의 길이 * 4) + (이전 도형 한 변의 길이 * 2)를 통해 구할 수 있다.

전체 코드

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solution(6));
    }
}

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

회고

처음에는 규칙을 ((현재 도형 한 변의 길이 + 이전도형 한변의 길이) + (이전도형 한변의 길이 + 이전이전도형 한변의 길이)) * 2의 규칙으로 문제를 접근했다.

코드는 다음과 같다.

class Solution {
    public long solution(int N) {
        List<Integer> no = new ArrayList<>();
        no.add(1);
        no.add(1);

        for (int i = 2; i < N; i++) {
            no.add(no.get(i-1) + no.get(i-2)); // 현재 값은 (이전 값 + 이전이전 값)
        }
        int currentNo = no.get(no.size() - 1);
        int preNo = no.get(no.size() - 2);
        return ((currentNo + preNo) + (preNo + no.get(no.size() - 3))) * 2;
    }
} 

결과는 맞았지만 효율성 체크에서 광탈..

아마도 이전 이전 도형까지 활용해서 효율성이 떨어진 것 같다.

그렇게 공책에 도형을 그려가며 생각을 해보니

(현재 도형 한 변의 길이 * 4) + (이전도형 한변의 길이 * 2)를 하면 둘레가 구해지겠다는 생각이 들었다.

왜 이렇게 가능할까?

아래 그림을 보자.

여기에서 3번째 도형의 둘레를 구하고 싶다고 가정하자.

위 공식을 적용하면 (2 * 4) + (1 * 2) = 10이 나온다.

(2 * 4)는 2번째 도형의 둘레를 만든다.

그 후 (1 * 2) 이전 도형 한 변의 길이를 2개 더해주면 다음과 같다.

이렇게 만든 도형은 그림과 같이 다음 도형이 되는 규칙이다.