백준 14501 파이썬 - 퇴사

 

14501번: 퇴사

최근에 순열 또는 조합 문제를 재귀로 푸는 연습을 하다보니, 이 문제에서도 비슷하게 적용했더니 답이 이상하게 나왔다.

그 이유가. 재귀 함수에서 재귀 호출을 for 반복문 내 에서 해서, 마치 순열 처럼 다음 인덱스를 바로 적용하는 것처럼 구현해서 답이 이상했던 것이었따.. ㅠ

상담기간이 1일이 아니기 때문에, 1일날 상담을 한다해도 그 다음날인 2일날에는 상담을 못할 수 있기 때문에, 순열과 다르게 중간 중간 뛰어넘기는 문제인다. 근데, 나는 처음에 순열처럼 풀었던 것이다..하하 평소보다 이른 아침 일찍 풀어서 그런지 미흡했다...

풀이

day: 재귀 함수 dfs 매개변수로, 해당 일을 뜻하는 index.

total: 재귀 함수 dfs 매개변수로, 현재 상담까지의 총 가격

ex) 1 째날 의 상담기간이 3일 이라면 다음 재귀함수 호출: dfs( 1일 + t[1], total + p[1] )

포인트 : 상담을 할 수도 있고, 안할 수도 있다.

 - 상담을 할 경우: dfs(day + t[day], total + p[day])

- 상담을 안하는 경우: dfs(day + 1, total) => 선택안하고 넘기는 것이기 때문에 날짜만 +1 해준다.

재귀 트리 그림 참고(글씨체는 바로바로 쓰느라 ㅠ)

index 보통 0부터 시작하는데 1일 2일 숫자를 신경쓰고 싶지않아서 위의 그럼처럼 0일부터 시작하는 것으로 간주했다.

코드

import sys
input = sys.stdin.readline

n = int(input())
p = []
t = []
ans = -1

def quit(day, total):
    global ans
    
    if day > n:
        return
    if day == n:
        ans = max(ans, total)
    else:
        quit(day + t[day], total + p[day])
        quit(day + 1, total)
for _ in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)
quit(0,0)
print(ans)