[자료구조] [python] [Dynamic Programming] Sherlock and Cost

Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 
https://www.hackerrank.com/challenges/sherlock-and-cost/problem?isFullScreen=true

 

- A Array의 앞에서부터 원소값을 결정한다고 하였을 때, A[i] - A[i-1]를 최대화 시키는 값을 가지는 A[i]의 경우의 수는 결국 A[i] =B[i] 이거나 A[i] = 1 이다. 이와 같은 성질을 이용하여, temp라는 임시 Array에 초기값이 (0, 0) 튜플을 원소로 가지는 배열을 만든다. 이 temp Array의 경우, 각 튜플의 첫번째 원소는 A[i]가 B[i]일 경우의 최대값을 저장하고, 두 번째 원소는 A[i]가 1일 때의 최대값을 저장한다. 그리고 최종적으로는 D[-1], 마지막 원소의 최대값을 최종 output값으로 산출한다. 

 

def cost(B, N):

    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])
    
    return max(D[-1])