프로그래머스 programers 타일장식물 (43104)문제의 풀이와 해설을 합니다.

[프로그래머스] 코딩테스트 연습 > 동적계획법(Dynamic Programming) > 타일장식물 (43104)

문제바로가기

이문제는 피보나치 수열 문제

|      |  3  |
| 5    |1| 2 |
|      |1|   |

처음 제공되는 정사각형 타일의 한변의 크기는 아래와 같이 제공된다.

[1, 1, 2, 3, 5, 8, …]

위 정사각형 한변의 크기는 피보나치 수열 인데 위 숫자가 해결해야될 수열이 아니라 n 차에서 4변의 합이 수열이다 약간 꼬아 놓은 문제

[1, 1, 2, 3, 5, 8]

위 와 같은 한변의 크기를 가진 정사각형의 둘레의 합은 결국 아래와 같고

[4, 6, 10, 16, 26, 42]

위 정사각형 둘레 값을 수열로 풀어야한다.

해결책

수열의 점화식을 도출 해보면

a1 = 4 (1+1+1+1)
a2 = 6 (2+2+1+1)
a3 = a2 + a1 (2+2+3+3 = 10)
…

결국 도출된 수열의 점화식은 아래와 같다.

an = a(n-2)+a(n-1)

소스코드

도출된 점화식을 재귀로 그대로 표현하면

class Solution {
    private static long[] memo = new long[80];
    public static long solution(int n) {
        if (n == 1) return 4;
        if (n == 2) return 6;
        if (memo[n] > 0) return memo[n];
        return memo[n] = solution(n - 1) + solution(n - 2);
    }
}