꿀잠

https://leetcode.com/problems/burst-balloons/description/

풍선을 터트리는 순서에 따라 얻는 점수가 다를 때 가장 크게 점수를 얻을 수 있는 방법에 대해 묻는 문제이다. DP 문제로 아이디어를 열심히 생각해 보았지만 잘 떠오르지 않아 해당 문제의 팁을 찾아보고 통과할 수 있었다.

풍선을 터트렸을 때 얻는 점수는 양쪽 좌우 잔여 풍선이 어떤지에 따라 다르다. 이 문제의 점화식의 아이디어는 특정 풍선을 터트릴 때 좌우로 구간이 나뉘며 문제를 작게 볼 수 있다는 점이다.

1 2 3 4 5 의 풍선이 있을 때 3을 터트릴 경우
1 2 - 3 - 4 5 문제를 3구간으로 나눌 수 있다.
1 2 구간의 최대 가능 점수, 3을 터트렸을 때의 점수, 4 5 구간의 최대 가능 점수이다.

이러한 사실을 이용해서 점화식을 세우고, 큰 구간의 점수를 계산하기 위해서 작은 구간의 최대 점수부터 차례대로 큰 구간의 점수를 찾아가는 형태의 순회를 해야 한다. 또한 주어진 조건에 따라 기본 풍선 점수 표 양 끝에 1점의 임의 점수를 추가해주면 문제를 코드를 작성하기에 편의성이 생긴다. 이러한 점들을 고려하며 통과한 최종 코드는 아래와 같다.

public class Solution {  
    public int maxCoins(int[] nums) {  
        int[] arr = new int[nums.length + 2];  
        for(int i = 0; i < nums.length; i++){  
            arr[i + 1] = nums[i];  
        }  
        arr[0] = 1;  
        arr[arr.length - 1] = 1;  
        int n = arr.length;  
  
        int[][] dp = new int[n][n];  
  
        for(int k = 0; k < n - 2; k++){  
            for(int l = 1; l + k <= n - 2; l++){  
                int r = l + k ;  
                for(int j = l; j <= r; j++){  
                    int front = dp[l][j - 1];  
                    int shoot =  arr[l - 1] * arr[j] * arr[r + 1];  
                    int back = dp[j + 1][r];  
  
                    dp[l][r] = Math.max(dp[l][r], front + shoot + back);  
                }  
            }  
        }  
  
        return dp[1][n - 2];  
    }  
  
}