[Python/HackerRank] Sherlock and cost

💬 문제

문제 난이도: medium

문제 링크: https://www.hackerrank.com/challenges/sherlock-and-cost/problem?isFullScreen=true

문제 설명

입력으로 1차원 배열 B가 주어진다.
배열 A는 B와 같은 길이의 배열로, 1<=A[i]<=B[i]인 조건을 만족한다.
이때 가능한 배열 A 중에서 연속한 원소의 차이의 합이 최대일 때 그 결과를 반환하라.

❗️접근 방법

DP(dynamic programming)

DP 테이블

dp[i][0]
: A[i]의 수가 1일 때, 배열 A[:i+1]까지 연속한 원소간 차이의 최대 합
dp[i][1]
: A[i]의 수가 B[i]일 때, 배열 A[:i+1]까지 연속한 원소간 차이의 최대 합

코드

def cost(B):
    N = len(B)
    if N == 1:
        return max(B)
    dp =[[0, 0] for _ in range(N)]
    dp[1][0] = abs(B[0] - 1)
    dp[1][1] = abs(B[1] -1)
    
    for i in range(2, N):
    	dp[i][0] = max(dp[i-1][0], dp[i-1][1] + abs(B[i-1]-1))
        dp[i][1] = max(abs(B[i-1] - B[i])+ dp[i-1][1] , abs(B[i]-1)+dp[i-1][0])
        
    return max(dp[N-1])

1. dp 테이블의 각 행이 [a,b]로 이루어져 있는 이유

궁극적으로 얻고 싶은 값은 차이의 최대 합이다.
따라서 1<=A[i]<=B[i]일때, A[i]는 1 또는 B[i]인 수임을 알 수 있다.
dp테이블도 A[i]가 1인 경우와 B[i]인 경우를 저장하기 위해 사용한다.

2. A[i]로 B[i]가 온다고 해서, A[i-1]은 무조건 1이어야 할까?

그렇다고 단정할 수 없다.
B[i-1] = 5이고, B[i]가 1일때는 abs(B[i-1]-B[i]) > abs(1-B[i])이지만
B[i-1] = 2이고, B[i]도 2일때는 abs(B[i-1]-B[i]) < abs(1-B[i])이다.
따라서 각 경우에 큰 값을 dp[i][0]과 dp[i][1]에 저장해줘야 한다.