프로그래머스 - 타일 장식물

문제

• 앵무조개의 나선 모양처럼 생긴 타일이 붙어있다. 타일이 N개일때 둘레의 길이를 구하라.

 

제한사항

• 1 <= N <= 80

예제

앵무조개 모양의 타일

타일 [1, 1, 2, 3, 5]가 붙어 있는 곳의 둘레는 빨간 선으로 표현되어있다.

빨간선으로 표현된 둘레의 길이는 26이다.

 

 

문제풀이

1. 가장 큰 두 숫자를 알면 둘레를 구할 수 있다. 두번째로 큰 타일은 a 첫번째로 큰 타일을 b라고 할 때, 가로 세로 중 넓은 변의 길이는 항상 a + b 짧은 변의 길이는 항상 b이기 때문이다.
2. 또한, b 다음으로 올 타일의 변의 길이 또한 a + b이다. 그러므로 [a, b] = [b, a + b]를 반복하여 계산하여 가장 큰 두 타일의 변의 길이를 구할 수 있다.

 

const getPerimeter = (x, y) => 2*x + 2*y

function solution(N) {
    if (N < 3) {
        return getPerimeter(1, N)
    }
    let a = 1, b = 1
    N -= 2
    while (N--) {
        [a, b] = [b, a + b]
    }
    return getPerimeter(b, a + b)
}

 

시간복잡도: O(N)

공간복잡도: O(1)

 

 

 

같은 로직으로 좀 더 간단하게 짜봤다.

 

const getPerimeter = (x, y) => 2*x + 2*y

function solution(N) {
    let a = 0, b = 1
    while (--N) {
        [a, b] = [b, a + b]
    }
    return getPerimeter(b, a + b)
}

시간복잡도: O(N)

공간복잡도: O(1)