[HackerRank] Sherlock and Cost

def cost(B):
    # Write your code here
    length = len(B)
    
    dp = [[0]*2 for _ in range(length)]
    
    for i in range(1,length):
        # A[i] == B[i]인 경우
        dp[i][0] = max(abs(B[i]-B[i-1])+dp[i-1][0], abs(B[i]-1)+dp[i-1][1])
        # A[i] == 1인 경우
        dp[i][1] = max(abs(1-B[i-1])+dp[i-1][0], dp[i-1][1] )
    
    return max(dp[length-1])

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

 

처음에 이 문제를 접했을 때 DP 알고리즘을 사용해서 풀려고 할 때 단순히 A[i]가 1인 경우와 B[i]인 경우 중 최댓값을 저장해가면서 풀려고 했었는데, 이 접근까진 맞았지만 모든 경우의 수를 고려해주지 않아 문제를 맞힐 수 없었다.

 

이 문제에서 DP 테이블을 저장할 시에 비교할 수 있는 경우의 수는 다음과 같이 총 4가지가 있다.

1. A[i] == B[i] 이면서 A[i-1] == B[i-1] 인 경우
2. A[i] == B[i] 이면서 A[i-1] == 1 인 경우
3. A[i] == 1 이면서 A[i-1] == B[i-1] 인 경우
4. A[i] == 1 이면서 A[i-1] == 1 인 경우

따라서 DP 테이블을 1차원 리스트가 아닌 2차원 리스트로 선언한 뒤에, dp[i][0] 에는 A[i] == B[i] 인 경우의 최댓값을, dp[i][1]에는 A[i] == 1인 경우의 최댓값을 저장해준다.

 

본인은 경우 2와 경우 3만 고려하였기 때문에, 즉 모든 경우의 수를 고려해주지 않았기 때문에 완벽하게 풀지 못하였다.

 

이번 문제를 풀면서 느낀 점은 DP 알고리즘을 사용할 때에는 작은 문제의 DP값을 활용하여 현재 문제의 DP값을 저장해야 한다는 점과, DP 테이블을 저장할 시에는 모든 가능한 경우의 수를 고려해야 한다는 것을 뼈저리게 깨달았다.

 

또한, DP를 사용한다고 함은 작은 문제에서부터 하나씩 값을 저장하되, 해당 위치에서는 모든 경우의 수를 고려해야 최적의 값을 저장해갈 수 있다는 것을 배울 수 있었다 :)