[JAVA] 프로그래머스 : 타일 장식물 (코딩테스트 고득점 kit > 동적계획법(Dynamic Programming))

https://programmers.co.kr/learn/courses/30/lessons/43104#qna

코딩테스트 연습 - 타일 장식물

동적계획법 문제를 풀기위해서는 큰 문제를 작은 문제로 나누는 과정이 필요함

이 과정을 통해 점화식을 세우는게 중요함

그리고 메모제이션을 해서 시간을 줄이는게 중요함
=>값을 저장해놓음으로써 함수 호출의 시간을 단축시킬수 있으므로

메모제이션 방법으로는 아래와 같은 방법이 있음 
1. 반복문을 이용하여 미리 값들에 대한 계산을 다 해서 저장하는 방법 (BOTTOM-UP)
2. 그 순간 필요하면 계산해서 저장하는 방법(TOP-DOWN)

 

해결 방안

1. 위의 그림을 통해 정사각형 한변의 길이는 N=1일 때 1, N=2일 때 1, N=3일 때 2와 같은 결과를 알 수 있고 이를 점화식으로 표현하게 되면 (N 번째 정사각형 한 변의 길이) = (N-2 번째 정사각형 한 변의 길이) + (N-1 번째 정사각형 한 변의 길이)가 됨

2. 이와 같은 점화식을 이용하여 input으로 주어진 1~N 번째까지의 정사각형 한 변의 길이를 구하고 메모제이션함
이때 메모제이션 방법으로는 반복문을 이용하여 미리 값을 계산해주는 BOTTOM-UP 방식을 이용함

3. n번째 정사각형까지 메모제이션한 data 배열을 이용하여 직사각형의 둘레를 구하는 방정식을 구하고 그에 값을 대입함
=> answer = 4*data[N] + 2*data[N-1]

 

코드

// 타일 장식물
class Solution {

    public long solution(int N) {
        long answer = 0;
        long[] data = new long[N+1];
        
        // dp(1)=1
        // dp(2)=1
        // dp(N)= dp(N-2) + dp(N-1)
        data[1] = 1;
        data[2] = 1;
        for(int i=3; i<data.length; i++){
            data[i] = data[i-2] + data[i-1];
        }
        
        // N개의 타일로 구성된 직사각형 둘레 : 4*data[N] + 2*data[N-1]
        answer = 4*data[N] + 2*data[N-1];
        
        return answer;
    }
}