[14501] 퇴사 (실버 3)

14501번: 퇴사

n개의 날짜와 걸리는 시간(T)과 보상(P)가 주어졌을 때, 일을 겹치게 할 수 없는 가정하에 가장 많은 보상을 받는 경우를 구하는 문제이다.

고려했던 사항은 다음과 같다.

• 1가지 일을 하는 도중에는 다른 일을 할 수 없다.

풀이 과정은 다음과 같다.

• 각 일을 (시작 날짜, 끝나는 날짜)를 key로, 보상을 price로 받는 reservations 딕셔너리를 구성한다.
• 빈 dp 딕셔너리를 구성한다.
• 정해진 기간(i, j)에 대해서 최대 이익을 찾는 함수를 구현한다.
  • i가 j보다 작다면 0을 반환한다.
  • dp에서 (i, j)값이 있다면 dp[(i, j)]를 반환한다.
  • 없다면 (i, j)에 껴 있는 reservations를 순회한다.
    • 껴 있는 날짜 (i1, j1)을 사이에 두고 옆에 양 옆(i, i - 1), (j + 1, j)에 대해서 각각 최대 이익을 찾는 함수를 재귀 호출한다.
    • 가장 큰 이익을 만드는 경우를 dp에 업데이트하고 반환한다.

처음에는 dfs로 접근하다가 잘 풀리지 않아서 문제의 분류가 dp인걸 보고 dp로 생각을 해보았다. dp가 될꺼라는 확신이 처음에 잘 서지 않았는데, 문제 풀기전에 좀 더 고민해볼 필요가 있다.(사실 그냥 실력이 없어서 경험이 필요하다...) 그리고, 다른 풀이를 보니 나와 다른 좀더 우아한 dp풀이가 있었다.(백준에 있는 많은 답안들이 비슷했다.)

import sys

def findMaxPrice(i, j):
  global dp, reservations

  if i > j:

    return 0
  if (i, j) in dp:

    return dp[(i, j)]
  price = 0
  for i1, j1 in reservations.keys():
    if i <= i1 and j1 <= j:
      price = max(price, findMaxPrice(i, i1 - 1) + reservations[(i1, j1)] + findMaxPrice(j1 + 1, j))
  dp[(i, j)] = price

  return dp[(i, j)]

n = int(sys.stdin.readline().strip())
dp = {}
reservations = {}
for i in range(n):
  dates, price = map(int, sys.stdin.readline().strip().split(' '))
  reservations[(i, i + dates - 1)] = price
answers = []
print(findMaxPrice(0, n - 1))

# 백준 풀이
n = int(input())

t = []
p = []
dp = []
for i in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)
    dp.append(b)
dp.append(0)
for i in range(n - 1, -1, -1):
    if t[i] + i > n:
        dp[i] = dp[i + 1]
    else:
        dp[i] = max(dp[i + 1], p[i] + dp[i + t[i]])

print(dp[0])