[python] 백준 - 14501. 퇴사

🤔문제 해결

• S4 | 완전탐색 or DP

난이도가 S4인 만큼 완전탐색으로 해결해도 된다.

하지만 저번에 한번 풀어봤으므로 이번에는 DP로 해결해봤다.

 

 

일하는 날을 맨 뒤에서부터 계산해보자

7일을 선택하면 근무시간 초과로 이익 0

6일도 마찬가지

5일을 선택하면 이익 15

4일을 선택하면 이익은 20에, 5일에도 일할 수 있으므로 +15 해서 35

3일을 선택하면 이익은 10에 4일에도 일할 수 있으므로 (4일에 일하면 위에서 확인했듯이 5일도 일한다) +35 이므로 45

2일을 선택하면 이익은 20

1일을 선택하면 이익은 10에 4일부터 일할 수 있으므로 ( 아까 그 35 를 더한다) +35 이므로 45

 

결과적으로 1,4,5 일하면 45

또는 3,4,5 일하면 45

이 두가지의 경우가 최대이다.

 

한가지 추가해야할 경우는 근무시간이 초과해서 일할 수 없더라도 0대신 현재나온 최대이익값을 채워넣어줘야한다.

 

💻소스 코드

import sys

input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())
    schedule = [tuple(map(int, input().split())) for _ in range(N)]
    profit = [0] * (N + 1)
    max_profit = 0
    for i in range(N - 1, -1, -1):
        day, money = schedule[i]
        if i + day > N:
            profit[i] = max_profit
            continue
        else:
            max_profit = max(money + profit[i + day], max_profit)
            profit[i] = max_profit
    print(max_profit)
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

링크: https://www.acmicpc.net/problem/14501

14501번: 퇴사