[BJ14501] 퇴사

🚩 문제 설명

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

14501번: 퇴사

⏱️ 시간 복잡도
▪O(N^2)

◾ 백준이가 얻을 수 있는 최대 수익을 구하는 문제

◾ 퇴사 날에는 탈출하고, 그 이전까지 일을 할 수 있습니다.

 

 

 

---

 

 

 

✅ 입출력

변수 설명

n : 일하는 총일, n+1날 퇴사

t p : n 개의 줄 (걸리는 기간, 받을 수 있는 금액)

return 벌수있는 최대수익

✔️ 예제 1

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

45

✔️ 예제 2

10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

55

✔️ 예제 3

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

90

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

n = int(input())  # 일 수
t = [0]  # 일하는 데 걸리는 시간
p = [0]  # 일하면 버는 수익

# 배열 입력
for _ in range(n):
    tmp = list(map(int, input().split()))
    t.append(tmp[0])
    p.append(tmp[1])


def dfs(day, tot):
    global ans

    # 퇴사날짜 이후면 탈출
    if day > n + 1:
        return

    # 해당 퇴사날짜라면
    if day == n + 1:
        ans = max(ans, tot)
        return

    dfs(day + 1, tot)  # 일을 하지 않는 경우
    dfs(day + t[day], tot + p[day])  # 일을 하는우경우


if __name__ == '__main__':
    ans = 0
    dfs(1, 0)
    print(ans)

💬 Point

➡️  재귀를 사용하여 수익을 구한다.
➡️  global ans

 

n = int(input())  # 일 수
t = [0]  # 일하는 데 걸리는 시간
p = [0]  # 일하면 버는 수익

# 배열 입력
for _ in range(n):
    tmp = list(map(int, input().split()))
    t.append(tmp[0])
    p.append(tmp[1])

◾ 입력을 받습니다. 각각 배열에 추가해줍니다.

 

def dfs(day, tot):
    global ans

    # 퇴사날짜 이후면 탈출
    if day > n + 1:
        return

    # 해당 퇴사날짜라면
    if day == n + 1:
        ans = max(ans, tot)
        return

    dfs(day + 1, tot)  # 일을 하지 않는 경우
    dfs(day + t[day], tot + p[day])  # 일을 하는 경우

◾ 만약 퇴사날짜 이후면 불가능한 경우이므로 탈출을 해야합니다. return 을 해줍니다.

만약 퇴사날짜가 된다면 최대값을 비교하여 구해봅니다.

 

◾ 일을 하지 않고 넘기는 경우도 세야합니다.

위 예시를 보면 ( day 1 -> day 6 -> day 7 : 50 + 10 + 20 = 80 ) 이 아니라 day 6 을 쉬고 수익을 더 벌 수 있는 day 8 에서 일을 할 수 있습니다. 그렇게 되면 (day 1 -> day 6 -> day 8 : 50 + 10 + 30 = 90 ) 80 이 아닌 90 을 벌 수 있게 됩니다.

 

dfs(day + 1, tot)  # 일을 하지 않는 경우
dfs(day + t[day], tot + p[day])  # 일을 하는 경우

◾ 따라서 일을 하는 경우와 일을 하지 않는 경우 모두 돌아줘야 합니다.

마치 이런 트리와 같은 형태인 것입니다. 두 가지의 경우를 dfs() 돌아 연결될 수 있도록 코드를 작성해줍시다.

 

 

 

 

 

 

 

 

 

 

 

 

# 알고리즘 백준 bj14501 퇴사 python dfs

# 알고리즘 백준 퇴사 파이썬 dfs 재귀

---