백준 14501 (퇴사 1), 15486 (퇴사 2)
백준 14501 (퇴사 1), 15486 (퇴사 2)
문제 링크
문제 링크 : https://www.acmicpc.net/problem/15486 문제 링크 : https://www.acmicpc.net/problem/14501
문제 접근
들어가기에 앞서, 14501과 15486은 같은 문제입니다.
오랜만입니다. 거의 2주 만에 포스팅을 합니다. 이런저런 약속때문에.. 아무튼 문제를 살펴보겠습니다.
상담원 백준이는 퇴사까지 남은 N일 동안, 최대한 많은 상담을 하려고 합니다. 왜냐하면 최대한의 이익을 보려고 하기 때문입니다. 하지만 각 상담에는 소요되는 시간이 존재합니다. 예시로 오늘 3일이 걸리는 상담을 한다고 가정해보면, 오늘과 내일과 모레는 다른 상담을 진행할 수 없습니다. 매일 주어지는 상담의 소요 시간 및 이익이 주어질 때, 최대한의 이익을 스케줄링하는 문제입니다.
그냥 매일 주어지는 상담을 한다고 하겠습니다. 즉 현재에 집중한다고 생각을 할 수 있습니다 (탐욕법). 근데 만약 오늘 주어진 상담이 시간은 엄청 걸리고, 이익은 매우 작은 상담이면 최대한의 이익을 받지 못합니다. 가성비(시간 대비 이익)가 떨어지기 때문입니다.
따라서, 매일 주어지는 상담을 그냥 할 것이 아닌, 적절히 걸러가면서 가성비가 좋은 상담을 해서, 최대 이익을 얻는 것이 목표라고 할 수 있겠습니다.
또한, 주어지는 N의 범위가 최대 1,500,000이기 때문에, 완전 탐색으로 푼다면 최적의 해는 구할 수 있겠지만 O(2^n)의 시간 복잡도를 가지는 굉장히 비효율적인 풀이가 될 것 입니다.
최대한의 이익을 구하는 문제에서, 최대 이익은 부분의 최대 이익으로 이루어져 있을 것이므로 다이나믹 프로그래밍(dp)를 활용해서 O(n)의 시간 복잡도를 갖도록 구현하였습니다.
각 state는 현재 날짜와, 현재 이익에 대해서 영향을 받는다는 것을 알 수가 있습니다. 그렇다면 dp table에 하루가 끝날 때, 최대 이익을 memo하면 될 것 같습니다. state에 대해 조금 더 살펴보자면 오늘 주어진 업무를 하는 경우와, 하지 않는 경우로 나뉩니다. 즉 오늘 주어진 업무가 끝나는 날을 future이라 하면, dp[future]은 dp[future]과, 오늘까지 최대 이익 max_profit + 오늘 주어진 업무에 대한 이익에 영향을 받는다는 것이죠. 전자는 오늘 주어진 업무를 하지 않는 경우고, 후자는 오늘 주어진 업무를 하는 경우라고 할 수 있겠습니다.
즉 점화식으로 표현한다면, dp[future] = max(dp[future], max_profit + today_profit)이라고 할 수 있겠습니다.
그렇다면 max_profit은 어떻게 알 수 있나요?
dp[today-1]이라고 할 수 있습니다. 왜냐하면 어제까지의 최대 이익이, 오늘 업무를 시작할 지 고려할 때 최대 이익이기 때문입니다. 아래 소스 코드를 참고하여주시길 바랍니다.
소스 코드
1번 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
n=int(input())
arr=[0 for _ in range(n+1)]
dp=[0 for _ in range(n+1)]
for i in range(1,n+1) :
t,p=map(int ,sys.stdin.readline().split())
arr[i]=[t,p]
for today in range(1,n+1) :
future=today+arr[today][0]-1
max_profit=dp[today-1] #dp[today-1]
if future<=n :
dp[future]=max(dp[future], max_profit + arr[today][1])
dp[today]=max(max_profit, dp[today])
print(dp[n])
입력을 먼저 다 받고, 계산을 하였습니다. 하지만 굳이 그럴 필요가 없습니다. 왜냐하면, 현재 시점에서 계산은 과거만 알면 되기 때문입니다. 따라서, 입력과 dp table 작성을 동시에 하도록 수정하였습니다.
2번 풀이
1
2
3
4
5
6
7
8
9
10
11
import sys
n=int(input())
dp=[0 for _ in range(n+1)]
for today in range(1,n+1) :
t,p=map(int ,sys.stdin.readline().split())
future=today+t-1
max_profit=dp[today-1] #dp[today-1]
if future<=n :
dp[future]=max(dp[future], max_profit + p)
dp[today]=max(max_profit, dp[today])
print(dp[n])
마무리하며
벌써 2월입니다. 시간이 참 빠른 것 같습니다. 방학 시작한 지 얼마 안 된 것 같은데 내일 수강신청을 합니다. 벌써 2024년도 한 달이 지나다니 세월이 무섭습니다.