[백준 14501번] 퇴사 - Python으로 구현하기

[백준 14501번] 퇴사 - Python으로 구현하기

 

문제 접근

• DP인지? 브루트포스인지?
• 입력값의 범위로 봐서 브루트포스로 해결 가능해 보인다.
• 해당 날짜에 상담을 진행하는 경우, 안하는 경우를 재귀적으로 구현하여 모든 경우를 다 보고 최대값만 뽑자

 

생각해볼 점

• dp로 어떻게 접근해야할지?

 

오답 분석

• 재귀 구현의 종료조건, 진행조건에 주의하기!

 

# 퇴사
n = int(input())
T = []
P = []
for _ in range(n):
    t,p=map(int,input().split())
    T.append(t)
    P.append(p)

ans = 0

# 종료 : index 가 n을 넘은 경우
# 진행 : index+t[i]가 n보다 작은 경우

def sol(index, profit):
    global ans

    if index > n:
        return
    if index == n:
        ans = max(ans, profit)
        return
    sol(index + 1, profit)
    sol(index + T[index], profit + P[index])

sol(0, 0)
print(ans)

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!