백준: 14501 퇴사

문제

14501번: 퇴사

 

문제 풀이

 N일 이후에 퇴사를 하는데, 그 전까지 할 수 있는 일들 중 최대 수익이 나는 경우의 수익의 합을 반환하는 문제이다.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

 위의 예시의 경우 6, 7에 상담하는 일은 퇴사 이후까지 일을 진행하여야 하므로 할 수 없다. 예시에서 가장 최대 수익을 발생시키는 경우는 1, 4, 5일에 상담하는 경우이다.

 

 상담을 하는 것에 대해 두 가지 경우가 있다. 첫 번째는 상담을 하는 것이고, 두 번째는 상담을 하지 않는 것이다. 이를 반영하여 경우의 수를 계산한다면 다음과 같이 계산 할 수 있다.

 

 그림과 같이 해당 일자에 상담을 하는가, 안하는가에 따라 (a), (b)와 같이 가지가 뻣는 것을 알 수 있다. 따라서 DFS를 일을 하는 경우와, 하지 않는 경우를 재귀 호출 하면 된다.

 

코드

from sys import stdin


def dfs(day, pay):
    global answer
    cur_pay, next_pay = pay

    if day >= n:
        if day == n:
            answer = max(answer, cur_pay + next_pay)
        else:
            answer = max(answer, cur_pay)
        return

    dfs(day + 1, pay)
    cur_pay += next_pay
    next_day, next_pay = works[day]
    dfs(day + next_day, [cur_pay, next_pay])


if __name__ == "__main__":
    answer = 0
    n = int(stdin.readline())
    works = [list(map(int, stdin.readline().split())) for _ in range(n)]

    dfs(0, [0, 0])
    print(answer)

 재귀호출을 종료하는 조건에서 n보다 큰 경우는 퇴사 이후의 일을 처리할 수 없으므로 현재까지 처리한 작업만 반영하여야 한다. DFS를 호출 할 때, 단순히 날짜만 증가시키는 경우가 해당 날짜의 일을 하지 않는 경우이다.