[Python](DFS) 백준 14501번 : 퇴사 (2가지 방법)

---

<접근 방법 1>

1. 문제에 있는 테이블 형태 그대로 Ti, Pi 리스트를 만든다.
2. 상담일을 선택할 수도, 아닐 수도 있는 모든 경우를 생각하므로 dfs를 이용한다는 생각을 떠올린다.
3. (DFS 안에서) 현재 날짜에서 걸리는 상담일을 더했을 때 마지막 날짜를 넘지 않을 경우,
   다음 dfs로 넘길 수 있다는 조건을 이용한다.
4. 또한, 현재 상담일을 사용하지 않고 다음으로 그냥 넘기는 경우도 고려해 준다.
5. 마지막 상담일에 다다랐을 때, answer를 cost의 최댓값으로 갱신해 준다.

Ti, Pi를 각기 다른 리스트로 정의

 

def dfs(n, cost):
    global answer
    if n == N:  # 마지막 상담일에 다다랐을 경우
        answer = max(answer, cost)
        return
    if Ti[n] + n <= N:  # 현재 날짜 + 걸릴 상담 기간 <= 마지막 상담일
        dfs(n + Ti[n], cost + Pi[n])
    dfs(n+1, cost)  # 상담을 선택하지 않고 다음날로 넘길 때


N = int(input())
Ti, Pi = [], []     # Ti : 상담 걸리는 기간, Pi : 받을 수 있는 금액
for _ in range(N):
    ti, pi = map(int, input().split())
    Ti.append(ti)
    Pi.append(pi)
# print("Ti :", Ti)
# print("Pi :", Pi)
answer = 0
dfs(0, 0)
print(answer)

---

<접근 방법 2>

1. Ti, Pi 테이블 정보를 각기 다른 리스트로 만들지 말고 하나의 리스트로 만든다.
2. 이하 동문

Ti, Pi를 하나의 info 리스트로 정의

def dfs(n, cost):
    global answer
    if n == N:  # 마지막 상담일에 다다랐을 경우
        answer = max(answer, cost)
        return
    if info[n][0] + n <= N:  # 현재 날짜 + 걸릴 상담 기간 <= 마지막 상담일
        dfs(n + info[n][0], cost + info[n][1])
    dfs(n+1, cost)  # 상담을 선택하지 않고 다음날로 넘길 때


N = int(input())
info = []
for _ in range(N):
    ti, pi = map(int, input().split())
    info.append([ti, pi])
#print("info :", info)
answer = 0
dfs(0, 0)
print(answer)

이해가 안되는 부분이 있으면 질문 주세요. 감사합니다.