14501번 - 퇴사

문제

 

14501번: 퇴사 (acmicpc.net)

14501번: 퇴사

풀이 1

테이블과 같이 소요시간과 보상이 주어졌을 때, 각 업무를 조합하여 경우들 중 최대값을 찾아내야 하는 문제이다. 가장 먼저, 조합의 경우를 찾는 방법을 바로 알아채기가 힘드니 주어진 예시를 가시화하여 상황을 정리해본다. 아래는 예시를 가시화하여 나타낸 그림이다.

위와 같은 업무 테이블을 이용해 7일차 까지 조합의 경우의 수 중 가장 큰 값을 찾아내야한다. 1일차 업무를 하고 받는 보상과 4일차 이후 부터의 조합 중 보상의 최대값을 더한 경우, 1일차 업무를 포기하고 2일차 혹은 3일차 업무를 하는 경우로 나뉜다. 이와 같은식으로 f(i)를 i일차 부터 시작해서 n일차 까지 가능한 업무 조합 보상 중 최대값이라 하면 다음 그림과 같이 표현된다.

이제 DP로 접근이 가능하다는 생각이 든다. i일차 업무에 k만큼의 시간 비용이 든다고 했을 때 다음과 같은 식이 세워질 수 있을 것이다.

• i 일차 업무가 가능할 때 : f(i) = max(p[1] + f(i+k), f(i+1), f(i+2), ... , f(i+k-1))
• i 일차 업무가 불가능할 때 : f(i) = max(f(i+1), f(i+2), ... , f(n))

코드

n = int(input())
t = [-1]
p = [-1]
for _ in range(n):
  cost,pay = map(int,input().split())
  t.append(cost)
  p.append(pay)

dp = [0]*(n+2)
max_pay = 0

for date in range(n,0,-1):
  if date + t[date]-1 <= n:
    dp[date] = max(p[date] + dp[date + t[date]], max_pay)
    max_pay = dp[date]
  else:
    dp[date] = max_pay

print(max_pay)

풀이 2

단순하게 DFS로 접근할 수 있다. 주의할 점은, 업무의 시간 비용이 1이면 그 업무는 당일 끝난다는 것이다. 따라서 재귀호출 시 해당 업무가 마지막 출근날짜를 넘기는지 확인할 필요가 있다.

N = int(input())
T,P = [],[]
for _ in range(N):
    t,p = map(int,input().split())
    T.append(t)
    P.append(p)


def dfs(start,result):
    global answer
    if start > N-1 :
        answer = max(answer,result)
        return
    for i in range(start,N):
        # 업무 종료 시간이 마지막날을 넘길경우
        if i+T[i]-1 > N-1:
            dfs(i+T[i],result)
        else:
            dfs(i+T[i],result+P[i])


answer = 0
dfs(0,0)
print(answer)