[Programmers] 타일 장식물 문제 풀이

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

피보나치 수열과 관련된 문제이다.

피보나치 수열을 이루는 직사각형을 연이어서 붙인다. 각 직사각형마다 사분원을 그려서 나선 모양이 되도록 이은 모양을 피보나치 나선이라고 한다. 이 문제에서는 각 직사각형을 타일 장식물이라고 부른다. 타일에 적힌 숫자는 각 타일의 한 변의 길이를 나타낸다. 타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 구하는 문제이다.

# 풀이

@Test
public void test() {
    assertThat(solution(5))
        .isEqualTo(26);
    assertThat(solution(6))
        .isEqualTo(42);
}

long[] dp;
public long solution(int N) {
    dp = new long[N + 1];
    return calculate(N);
}

private long calculate(int N) {
    if(N == 1) {
        return 4;
    }
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i < N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return (dp[N - 1] + (dp[N - 1] + dp[N - 2])) * 2;
}

N에 전달되는 값은 1이상 80이하인 자연수가 주어진다. 직사각형 타일의 둘레는 (가로 길이 + 세로 길이) * 2) 의 공식을 이용하여 구할 수 있다.

직사각형에서 한 변의 길이와 세로 길이는 같다. 가로 길이는 한 변의 길이와 이전 단계의 직사각형의 한변의 길이를 더한 것과 같다. 그림에서 빨간색으로 표시된 직사각형은 N = 4인 직사각형 타일을 의미한다. N = 4의 한 변의 길이는 5, N = 3의 한 변의 길이는 3이므로 직사각형의 둘레는 26이 된다.

N은 타일의 개수를 의미하며 1부터 시작하지만 피보나치 수열 0부터 시작한다. 따라서 N개의 타일은 N - 1번 째 피보나치 수를 의미한다.

# 배운 점

피보나치 수열로 나선 모양을 그릴 수 있다는 것과 DP 문제를 어떤 방식으로 접근하는가에 대한 감을 잡았다. 구간합, 체를 이용한 소수 판단 문제와 비슷하게 미리 계산된 값을 이용해 복잡도를 줄이는 것이 관건이다.