[백준 17979번] [동적 계획법] What’s Mine is Mine

상당히 어려운 문제이다.

 

이 문제를 보고 DP를 느끼는 것이 매우 어려운데, 각각의 타이밍마다 선택하는 기준이 앞의 선행조건에 의해 영향을 받는다는 점에 착안하여 DP 문제임을 인지하면 된다. 

 

예를 들면

N시에 어떠한 광물을 채굴할지의 여부는 일단 전체 집단에서 N시에 끝나는 지를 확인하고 없으면 N-1시 까지의 최대 최굴량과 동일하다.

만약 존재하는 경우, 해당 시작시간이 M이라 가정하면 N - M시의 최대 최굴량에서 추가되는 최굴량을 더해준 것과 같다.

 

만약 N시에 끝나는 경우가 많은 경우에는 최댓값을 기준으로 결정해주면 된다.

 

즉, N시에서의 최대 최굴량을 구하는 과정에서 N.- M시의 최대 최굴량이 들어가게 되므로 DP를 활용하면 쉽게 구할 수 있음을 이 과정에서 느껴야 한다.

 

// 다만, N시에 끝나는지를 데이터 전체를 탐색하면 매우 오래 걸리므로 Data를 입력받을 때 몇시에 끝나는지를 따로 배열로 정리하여 바로 참조할 수 있도록 하는 것이 시간적으로 매우 유리하다. (처음에 이것을 발견을 못하여 시간초과가 나왔으므로 많이 복습해야 한다.)

 

위의 내용을 코드로 옮기면 다음과 같다.

import sys

# Default setting

m, n = map(int, sys.stdin.readline().split())

money = [0] * (m + 1)

data = [0] * (n + 1)
data[0] = [None, None, None]
end_data = [0] * 15001

for i in range(15001):
    end_data[i] = []

for i in range(1, m + 1):
    value = int(input())
    money[i] = value

# End data store seperately

for i in range(1, n + 1):
    data[i] = list(map(int, sys.stdin.readline().split()))
    end_data[data[i][1]].append(i)

# Dynamic programming (small to large)

dp = [0] * 15001
initial = 1

while initial <= 15000:
    store = []

    if len(end_data[initial]) == 0:
        dp[initial] = dp[initial - 1]

    else:
        for i in range(len(end_data[initial])):      
            store.append(dp[data[end_data[initial][i]][0]] \
            + (initial - data[end_data[initial][i]][0]) \
            * money[data[(end_data[initial][i])][2]])
        
        # Compare the maximum result and store
        
        if dp[initial - 1] < max(store):
            dp[initial] = max(store)
        else:
            dp[initial] = dp[initial - 1]

    initial += 1

# Print result

print(dp[15000])

자주 나오는 유형이라고 할 수 있겠다.