[백준][python]14501 퇴사

문제

https://www.acmicpc.net/problem/14501

소스코드1 : DFS

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    schedule = [list(map(int,input().split())) for _ in range(n)]
    visited = [False for _ in range(n)]
    res = 0

    def dfs(today, total,lastdaypay):
        global res
        if today > n:
            res = max(res,total-lastdaypay)
            return
        elif today == n:
            res = max(res,total)
            return

        for i in range(today,n):
            if not visited[i]:
                visited[i] = True
                dfs(i + schedule[i][0], total + schedule[i][1],schedule[i][1])
                visited[i] = False

    dfs(0,0,0)
    print(res)

설명

n이 15개뿐이 안되서 백트래킹을 이용해서 DFS 탐색을 했다

오늘 날짜 + 상담 날짜가 퇴사일을 넘어버리면 그 전 잡은 상담은 하지 못하므로 total에서 lastdaypay(직전 더해준 값)을 빼버린다

오늘 날짜 + 상담 날짜가 퇴사일이면 상담을 할 수 있으므로 total을 계산해준다.

 

소스코드 2 : DP

if __name__ == "__main__":
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)] #상담에 걸리는 시간, 상담 비용
    dp = [0] * (n+1)

    for day in range(n-1,-1,-1):
        if day + arr[day][0] > n : #현재 날짜와 상담 날짜를 더해서 퇴사날이면
            dp[day] = dp[day+1] # 그동안 누적된 비용을 그대로 가져감
        else:
            dp[day] = max(dp[day+1],dp[day+arr[day][0]] + arr[day][1]) #상담을 했을 때 비용과 상담 안했을 때 지금까지 누적값중 더 큰 값으로 교체

    print(dp[0])

설명

bottom-up 방식으로 누적값을 더해 가장 마지막날부터 체크해서 첫번째 값이 최종 누적 값이다.

0부터 하면 안되는 이유는 0일 일 때 5일을 상담하면 누적하다 5일이 오면 누적된 최종 값이 5일이 포함된 값인지 아닌지 알 수 가 없다

마지막날 부터 체크해주면 dp를 구할 때 중복되는 값을 제거해줄 수 있다.

dp[day] = max(dp[day+1],dp[day+arr[day][0]] + arr[day][1])

• 이전에 누적된 값
• 오늘 날짜에 상담한 날짜를 더한 날의 pay + 오늘 상담을 하고 받은 pay

을 비교해서 더 큰 값을 dp 에 넣어줌으로써 중복된 값을 제거할 수 있다.

dp를 저장하는 내용을 표에 그려보면 아래와 같다.

 

7일일 때, 7 + 2 는 퇴사 날짜가 지나므로 그 전까지의 pay를 가져온다

6일일 때, 6 + 4 는 퇴사 날짜가 지나므로 그 전까지의 pay를 가져온다

5일일 때, 5 + 2 는 퇴사전이므로 상담을 할 수 있다. 그전까지의 누적합과 오늘 pay + (5+2)일의 누적 pay 중 큰 값을 가져온다. 

위와 같은 방식으로 체크하면 최종 1일에 있는 값이 중복이 되지 않고 가장 돈을 많이 받고 상담을 하는 금액이 된다.