[JS] 프로그래머스 보물 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/468378

프로그래머스

 

어렵다.

 

해당 문제는 "최소의 비용"으로 보물을 찾는 문제였다.

먼저 그리디, 이분 탐색 모두 실행해봤지만 실패였다. (최악의 경우를 대비하지 못한다.)

 

따라서 미리 최악의 비용을 계산한 뒤에

최악의 비용이 최소인 곳으로 검사하는 방향으로 설계해야 한다.

그 말인 즉슨 dp를 사용했다.

 

dp를 3차원으로 설계하고

dp[구간 시작점][구간 끝점] = [최악의 비용, 최악의 비용일 때의 인덱스]로 초기화했다.

 

1. 구간의 길이가 0일 때 초기화했다. dp[start][start][0] = depth[start]; dp[start][start][1] = start;

2. 삼중 반복문을 돌면서 최악의 비용인 최소인 값과 인덱스를 갱신했다.

구간의 길이[1, n-1] -> 시작점[0, 0 + 구간의 길이] -> 구간 안의 특정 인덱스

 

구간 안의 특정 인덱스의 경우

1) 왼쪽 부분, 자기 자신

2) 자기 자신, 오른쪽 부분

3) 왼쪽 부분, 자기 자신, 오른쪽 부분

이렇게 나눠서 최악의 비용을 구했다.

 

3)번과 같은 경우 왼쪽 부분과 오른쪽 부분의 최악의 비용을 가져와야 했으므로

Math.max()를 사용하여 구했다.

(자세한 것은 코드를 참고하라!)

 

이렇게 최악의 비용과 기존 값을 비교해서

기존 값보다 작은 경우 인덱스와 값 모두 갱신했다.

 

이렇게 dp가 끝났다.

 

따라서 투 포인터를 통해 파악할 다음 인덱스를 알아봐야 한다.

left, right 인덱스를 각각 양 끝 점으로 초기화해서 while 문을 돌린다. (left <= right이다. 같은 경우도 고려해야 한다!)

1) 현재 구간에서의 최악의 비용이 최소인 인덱스 파악

2) 함수 돌려서 0이라면 인덱스 + 1 파악 (주의해야 한다. 반환값은 1-index이다.)

-1 -> right = 인덱스 - 1

1 -> left = 인덱스 + 1

 

이렇게 하면 된다. 말도 어렵다. 자주 볼 것!

 

(참고: 운에 맡기지 않고 100% 확률로 보물을 찾기 위한 최소 비용 ≤ money 이므로 엣지 케이스는 고려하지 않아도 된다.)

/*
설계: 최소 비용 안에서 보물 찾기
dp 항상 최악의 비용을 고려해야 하게 때문에
미리 이중 반복으로 순회하면서 계산해 놓기.

0, 1, 2
하나만 판단하면 된다.
*/

function solution(depth, money, excavate) {
    const n = depth.length;
    
    // [left][right]까지의 비용
    const dp = Array.from({length: n}, () => Array.from({length: n}, () => [Infinity, -1]));
    
    // 구간의 길이가 0인 경우 depth
    for (let start = 0; start < n; start++) {
        dp[start][start][0] = depth[start];
        dp[start][start][1] = start;
    }
    
    // 구간의 길이 -> 시작점 -> 구간안의 k
    for (let len = 1; len < n; len++) {
        for (let start = 0; start + len < n; start++) {
            let curr = dp[start][start + len][0];
            let i = dp[start][start + len][1];
            
            for (let k = start; k <= start + len; k++) {
                let contrast = Infinity;
                
                // 오른쪽만 고려
                if (k === start) {
                    contrast = depth[k] + dp[start + 1][start + len][0];
                }
                // 왼쪽만 고려
                else if (k === start + len) {
                    contrast = depth[k] + dp[start][start + len - 1][0];
                }
                // 나머지
                else {
                    contrast = depth[k] + Math.max(dp[start][k - 1][0], dp[k + 1][start + len][0]);
                }
                
                // 최악의 비용 산출
                if (curr > contrast) {
                    i = k;
                    curr = contrast;
                }
            }
            
            dp[start][start + len][0] = curr;
            dp[start][start + len][1] = i;
        }
    }
    
    // dp 완성 후 excavate 실행
    let left = 0;
    let right = n - 1;
    
    while (left <= right) {
        // 현재 비용이 최소인 인덱스 구하기
        const idx = dp[left][right][1];
        
        // 검사하기 1-index로 변환
        const result = excavate(idx + 1);
        
        if (result === 0) return idx + 1;
        else if (result === -1) {
            right = Math.max(0, idx - 1);
        } else if (result === 1) {
            left = Math.min(n - 1, idx + 1);
        }
    }
    
    return 0;
}