[코딩 인터뷰][HackerRank] Sherlock and Cost

Posted on by

※ 이 포스트는 HackerRank 문제인 Sherlock and Cost의 해설을 다루고 있습니다.
본 포스팅의 풀이는 Optimal하지 않을 수 있으며, HackerRank에서의 Submission 통과만을 보장합니다.

Sherlock and Cost

문제 출처 : https://www.hackerrank.com/challenges/sherlock-and-cost/problem
카테고리 : DP
난이도 : Medium (50 point)

문제 설명

자연수 배열 B가 주어진다. 이 B로부터 새로운 배열 A를 정의한다. 모든 배열의 원소 A[i]는 1 <= A[i] <= B[i]를 만족해야한다. 이 조건 상에서 만들 수 있는 A중에서 sum(|A[i] – A[i – 1]|)의 최댓값을 구하여라.

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

문제 풀이

아무것도 없는 배열에 왼쪽부터 하나씩 원소를 추가한다고 생각하자. 그럴 때 매 추가마다 새로운 |A[i] – A[i – 1]|이 계산된다. 이 때 A[i]가 A[i – 1]보다 커야 한다면 A[i]는 가능한 최대 크기를 갖는게 좋다. 반대로 A[i]가 A[i – 1]보다 작다면 가능한 최소 크기를 갖는게 좋다. 따라서 A[i]가 1이나 B[i]와 동일한 두 경우가 남게 된다.

이 논리가 일관적으로 적용되므로 A[i – 1] 또한 1이나 B[i – 1] 중 하나의 값을 가져야만 할 것이다. 2차원 배열 D를 정의한다. D[i][0]은 A[i] = B[i]일 때의 A[0 ~ i]에 대한 최댓값이고, D[i][1]은 A[i] = 1일 때의 A[0 ~ i]의 최댓값이다.

A[i][0]에 대해서는 |B[i] – B[i – 1]| + D[i – 1][0]이나 |B[i] – 1] + D[i – 1][1] 중 큰 것이 정답이 된다.
A[i][1]에 대해서는 |1 – B[i – 1]| + D[i – 1][0]이나 |1 – 1| + D[i – 1][1] 중 큰 것이 정답이 된다.

이 작업을 반복한 후 D의 마지막 원소에 대해 두 경우 중 최댓값을 출력하면 된다.

코드
#!/bin/python3

import os
import sys

# Complete the cost function below.

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        N = int(input())
        B = [int(x) for x in input().split()]
        D = [[0] * 2 for i in range(N)]
        for i in range(1, N):
            # In case A[i] = B[i]
            D[i][0] = max(abs(B[i] - B[i - 1]) + D[i - 1][0], abs(B[i] - 1) + D[i - 1][1])

            # In case B[i] = 1
            D[i][1] = max(abs(1 - B[i - 1]) + D[i - 1][0], D[i - 1][1])

        result = max(max(D))

        fptr.write(str(result) + '\n')

    fptr.close()

코딩 인터뷰 – Sherlock and Cost