[BOJ / Python] 15486 퇴사 2

🧩 문제 : 15486 퇴사 2

 

👩🏻‍💻 문제 정리 

백준이가 일을 하는 데 걸리는 시간 T와 일을 하고 나서 얻는 수익 P를 고려해 N일 동안 얻을 수 있는 최대 수익을 구하면 된다. 

 

 

---

 

💪🏻 풀이 과정 

다음 예시를 살펴보자.

 

백준이는 7일간 근무를 할 수 있으므로 1 ~ 7일까지의 수익을 계산할 배열을 만들어줘보자. 

 

1일에 잡힌 상담을 살펴보자. 

걸리는 시간은 3일이고 얻을 수 있는 수익은 10만원이다. 

따라서 3일 뒤인 3일에 10만원을 벌 수 있으므로 다음과 같이 배열의 값을 입력해준다. 

 

두번째, 2일에 잡힌 상담을 살펴보자.

5일 일해서 20만원을 벌 수 있다. 따라서 6일에 20만원을 얻을 수 있다. 

 

세번째, 3일에 하루 일해서 10만원을 벌 수 있다. 

하지만 이미 1~3일에 일을 하고 있으므로 일을 할 수 없다. 

 

네번째, 4일에 하루 일해서 20만원을 벌 수 있다. 

그런데 3일까지 일하고 4일에 또 일하면 10 + 20 = 30만원을 벌 수 있으므로 최대 수익은 30이다. 

 

다섯번째, 5일부터 이틀 일하면 15만원을 벌 수 있다. 

즉 6일에 15만원을 벌 수 있다. 하지만 1~3일에 일하고, 4일에 일하고, 5~6일에 일을 하면 총 45만원을 벌 수 있다.

 

그 다음으로 6일부터 사흘간, 7일부터 이틀간 걸리는 일이 있지만 퇴사를 하기 때문에 해당 일을 할 수 없다.

따라서 백준이의 최대 수익은 45만원이 된다. 

 

 

💡 문제 포인트

1️⃣ 퇴사날에는 일을 할 수 없다.

2️⃣ 전 날까지 얻은 수익을 합할 수 있다. 

for i in range(1, N + 1):
    end_day = i + T[i] - 1 # 일을 끝낼 수 있는 날
    if end_day <= N: # 퇴사 하기 전이라면
        pay = dp[i - 1] + P[i]
        dp[end_day] = max(dp[end_day], pay)

 

 

💻 코드

1️⃣ 첫번째 코드 - 틀렸습니다. 

import sys

input = sys.stdin.readline

N = int(input())
T = [0]
P = [0]
dp = [0] * (N + 1)

# 입력
for _ in range(N):
    x, y = map(int, input().split())
    T.append(x)
    P.append(y)


for i in range(1, N + 1):
    end_day = i + T[i] - 1 # 일을 끝낼 수 있는 날
    if end_day <= N: # 퇴사 하기 전이라면
        pay = dp[i - 1] + P[i]
        dp[end_day] = max(dp[end_day], pay)

print(max(dp))

왜지?

 

 

.

.

.

 

🌱  내가 빼먹은 것

기존의 내가 생각한 아이디어 에서는 5일째에 수익이 0으로 나타나지만, 

5일에 일을 하지 않더라도 4일까지 일한 수익을 얻을 수 있음 ! 이 점을 고려해야함

즉, i일에 얻을 수 있는 이익은 그 전날 얻을 수 있는 이익과 같거나 크다.

 

2️⃣ 두번째 코드 - 맞았습니다. 

import sys

input = sys.stdin.readline

N = int(input())
T = [0]
P = [0]
dp = [0] * (N + 1)

# 입력
for _ in range(N):
    x, y = map(int, input().split())
    T.append(x)
    P.append(y)


for i in range(1, N + 1):
    dp[i] = max(dp[i], dp[i - 1]) # i일의 수익 갱신
    end_day = i + T[i] - 1 # 일을 끝낼 수 있는 날
    if end_day <= N: # 퇴사 하기 전이라면
        pay = dp[i - 1] + P[i]
        dp[end_day] = max(dp[end_day], pay)

print(max(dp))

 

 

💭결과