Sherlock and Cost

사이트: HackerRank
난이도: 미디움
분류: Dynamic programming

문제

숫자 배열 B가 주어질때 새로운 배열 A를 만들 수 있는데, A의 각 원소들은 1 <= A[i] <= B[i] 식을 가진다. 이런 특성을 가진 A 배열 중 |A[i] - A[i - 1]| 의 최대 합을 구하는 문제이다.

예를 들어서 B = [20, 20, 20] 이라고 한다면 A = [20, 1, 20]이 |20 – 1| + |1 – 20| = 38의 최댓값을 만들 수 있는 배열이다.

1. 나의 풀이

어려웠던 점

A[i]와 A[i - 1]의 차이를 크게 만드려면 둘 중 작은 요소의 값을 1로 설정해야 한다는 추론까지는 하였다. 어려웠던 점은 이전 값이 B[i - 1]인지 1인지 어떻게 기억해야 할까를 고민했던 것이었다.
해당 고민이 계속 지속됐던 것은 DP의 특성을 아직 잘 이해하지 못하고 접근했기 때문인 것 같다. 결국 중요한 것은 현재 요소의 B[i] - B[i - 1]과 1 - B[i - 1]의 크기 값을 계속 비교하는 것이었고, 거기서 끝이 아니라 이전 요소의 1 - B[i - 1]의 값도 계속 저장해두고 다음 요소의 계산식으로 활용 하는 것이었다.
따라서 A[0 ~ (i - 1)]까지의 값은 자연스럽게 검증 되고 신경 써야 할 것은 현재 요소 A[i]와 이전 요소 A[i - 1]의 최대 합만 신경쓰면 될 문제였던 것이다.
DP 알고리즘 문제는 해당 문제와 같이 현재 내가 계산해야될 요소(작은 문제)만 신경쓰고 이전 값들은 계속 재사용하는 형태로 풀이되는 경우가 많은 것 같다. 다음 DP 문제에서는 이런 규칙들을 잘 인지하고 접근해야 할 것 같다.

2. 다른사람의 풀이

DP를 활용하여 dp[0][i]를 계속 저장해 두고 가장 큰 값을 선택하는 과정을 반복하는 문제이다.
문제의 특성상 A[i]와 A[i - 1]를 비교하여 가장 큰 값이 되는 수를 선택하고 보다 작은 수를 가진 요소는 1을 선택하여 그 차이를 최대한 큰 값으로 계산하는 것이 중요하다.
dp[0][i]는 A[0 ~ i] 까지의 최대 합을 저장해 놓을 변수이다. 여기서 한가지 판단을 해주어야 할 것이 있는데, A[i - 1]이 1로 연산된 결과와 A[i - 1] === B[i - 1]로 연산된 결과 중 가장 큰 값을 선택해야 하는 것이다.

dp[0][i] = Math.max(
	dp[0][i - 1] + Math.abs(B[i] - B[i - 1]), 
	// A[i - 1]이 1이기 때문에 dp[1]의 값을 가져온다.
	dp[1][i - 1] + Math.abs(B[i] - 1)
);

위 식에서 한가지 의문이 드는 것이 이전 최대 합 + |B[i] - B[i - 1]| 식인데, 추론한 대로 생각했을 때, B[i] - 1 또는 1 - B[i - 1]로 식을 설정해야 할 것으로 예상이 된다. 그러나 풀이에서는 그냥 B[i] - B[i - 1]로 써버렸다.
왜 현재 요소는 1 또는 B[i]가 아닐까?
정답은 단순히 현재 요소가 1이라고 해서 항상 큰 차이 값을 만들 수 없기 때문이다.

dp[1][i]는 A[i]가 1이 되고 A[i - 1] === B[i - 1]이 되는 경우 A[0 ~ i] 까지의 합을 저장해 놓을 변수이다. 따라서 아래와 같은 식을 가지게 된다.

dp[1][i] = dp[0][i - 1] + Math.abs(1 - B[i - 1]);

전체 코드는 아래와 같다.

function cost(B) {
    const n = B.length;
    const dp = [];

    dp[0] = [0];
    dp[1] = [0];
    
    for (let i = 1; i < n; i++) {
        dp[0][i] = Math.max(
            dp[0][i - 1] + Math.abs(B[i] - B[i - 1]), 
            dp[1][i - 1] + Math.abs(B[i] - 1)
        );
        dp[1][i] = dp[0][i - 1] + Math.abs(1 - B[i - 1]);
    }

    return Math.max(dp[0][n - 1], dp[1][n - 1]);
}

결론

여기서의 작은 문제는 A[0 ~ i]까지의 최대합이다.