Coding Interview

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

※ 이 포스트는 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

admin

Recent Posts

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

3일 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

3주 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

2개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

2개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

2개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

This website uses cookies.