백준 14501. 퇴사 (Python)

문제 링크는 여기!

14501번: 퇴사

 

*문제의 저작권은 모두 스타트링크에 있습니다.

 

 사실 A 형 문제에 이런 문제 나와주면 좋겠다. 탐색 방법만 알면 바로 끝낼 수 있는 문제입니다!

swea 1952번(수영장) 과 굉장히 비슷한 간단한 백트래킹문제입니다!

만약에 N의 값이 커지면 dp로 풀어야 할 것 같은데, 백트래킹 하나만 해주면 바로 dfs로 풀 수 있는 문제!

백트래킹 많이 하지 않고 dfs 제출했는데 156ms였는데 제출시간도 2초일 정도로 아주 넉넉하다!

 

 

아이디어

 1. 그 날짜 상담을 안 받는 경우로 dfs를 한번 진행해주고

 2. 만약에 상담을 할 수 있는 날이면 (해당날짜 + 걸리는 시간 < 총 날짜) 상담 받는 탐색 돌려주기!

 

 

#백준 14501 퇴사

def revenue_making(idx, rev):
    global max_rev
    if idx == N:
        if max_rev < rev:
            max_rev = rev
        return
    revenue_making(idx+1, rev) #상담을 안 받는 경우
    if idx + table[idx][0] <= N: #상담을 해줄 수 있는 경우
        revenue_making(idx+table[idx][0], rev+table[idx][1])

N = int(input())
table = []
for i in range(N):
    t, p = map(int, input().split())
    table.append((t,p))
max_rev = 0
revenue_making(0, 0)

print(max_rev)