-
[자료구조] [python] [Dynamic Programming] Sherlock and CostData miner/Algorithm & Data structure 2022. 2. 14. 13:24728x90
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])
'Data miner > Algorithm & Data structure' 카테고리의 다른 글
[백준] [DP] 제곱수의 합 (0) 2022.11.11 [백준] [DP] 연속합 / 리스트의 임의의 수열에서 연속된 합의 값 중 최대값 찾기 (0) 2022.11.07 [자료구조] [python] [Dynamic Programming] Equal (0) 2022.02.12 [자료구조] [python] [Dynamic Programming] The Coin Change Problem (1) 2022.02.08 [자료구조] [python] [Search] Cut the Tree (0) 2022.01.24