BOJ #14501 퇴사

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 14501. 퇴사

문제 풀이

백트래킹으로 풀 수 있을거라 생각했지만 DP처럼 접근해서 해결해야 하는 문제였다.

• i번째 날의 경우 해당 날짜에 일을 할 것인지, 일을 하지 않을 것인지 두 가지 선택지가 존재한다.
• 일을 할 경우 받을 수 있는 대가를 체크하고 일이 종료되는 날짜로 넘어간다
• 일을 하지 않을 경우 그대로 다음 날짜로 진행한다.
• 종료 시점은 날짜가 N + 1일 째 일을 할 수 없으므로 입력받은 기존 최대값과 종료시점에서의 최대값을 비교하여 반환한다.
• 모든 재귀 함수가 종료되면 이제까지의 최대값을 반환하여 모든 루틴을 끝낸다.

백트래킹으로 작성하면 해당 날짜에 일을 할 수 있는지 없는지 체크한 뒤 일을 해보고 최대값을 갱신한 뒤 해당 일을 하지 않겠다고 취소하는 방식이었지만 문제는 마지막 종결조건과 중간에 날짜를 기록하면서 코드가 굉장히 복잡해졌다.

python 코드

from sys import stdin
input = stdin.readline

N = int(input())
nums = [(0, 0)] # 0번째 날 패치
for i in range(N): # 1번 일부터 N일까지 더하기
    length, cost = map(int, input().split())
    nums.append((length, cost))

def dfs(i, sum, ans):
    if i == N + 1: # 날짜가 종료되어 최종 결산
        ans = max(ans, sum) # 최대값 반영
        return ans
    if i + nums[i][0] <= N + 1: # i번째 날 일을 한다면
        ans = dfs(i + nums[i][0], sum + nums[i][1], ans)
    if i + 1 <= N + 1: # i번째 날 일을 하지 않는다면
        ans = dfs(i + 1, sum, ans)
    return ans # 최대값 반환

print(dfs(1, 0, 0))