[HackerRank] Sherlock and Cost

Practice > Algorithm > Dynamic Programming

문제

code

int cost(int B_count, int* B) {
    int dp[3][100001] = {0};
    int max = 0;
    for(int i=1; i<B_count; i++){
        dp[0][i] = abs(1 - B[i-1]) + ((dp[1][i-1] > dp[2][i-1]) ? dp[1][i-1] : dp[2][i-1]);
        dp[1][i] = abs(B[i] - B[i-1]) + ((dp[1][i-1] > dp[2][i-1]) ? dp[1][i-1] : dp[2][i-1]);
        dp[2][i] = abs(B[i] - 1) + dp[0][i-1];
    }
    
    for(int i=0; i<3; i++)
        if(max < dp[i][B_count-1])
            max = dp[i][B_count-1];
    
    return max;
}

• 최대값을 가지도록 할 때 3가지 케이스로 나눌 수 있다.

1. B[i-1] - 1 : 뒤 원소를 1로 취급하고 차를 구하기
2. B[i-1] - B[i] : 배열의 원소끼리 차를 구하기
3. 1 - B[i] : 앞에 원소가 1이기 때문에 최대인 현재 원소와 차를 구하기

• 이때 1과 2의 경우 dp[1][i-1] 또는 dp[2][i-1] 중 더 큰 값을 선택한다.
• 3의 경우 한 가지 경우밖에 없기 때문에 그냥 차를 구해 더한다.
• 마지막으로 dp[0][B_count-1], dp[1][B_count-1], dp[2][B_count-1] 중 제일 큰 값을 찾아 반환하고 함수를 종료한다. 

결과