🧩 문제 : 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))
💭결과
'알고리즘' 카테고리의 다른 글
[BOJ / Python] 9372 상근이의 여행 (0) | 2023.02.20 |
---|---|
[프로그래머스 / Python] 순위 (0) | 2023.02.14 |
[BOJ / Python] 2022 사다리 (0) | 2023.02.09 |
[BOJ / Python] 3107 IPv6 (0) | 2023.02.08 |
[BOJ / Python] 25603 짱해커 이동식 (0) | 2023.02.07 |