퇴사 백준 14501번 DP

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

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자.

최대한의 효율로 끌어내는 문제인데 보통 그리디와 DP 두가지로 접근하게 됩니다.

이것과 비슷한 유형의 문제로 가방에 물건 집어넣기, 동전 최소의 개수로 거슬로 주기, 지금 풀게 되는 일정 상담 예약잡기인데 모두 같은 알고리즘으로 풀 수 있습니다.

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

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다. 또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

뭔가 이렇게 점화식을 이용하거나 인적성 NCS 수리 문제 파트에서 종종 본기억이 나네요

이것도 앞에서 금광이나 정수 삼각형과 접근 방법 자체는 비슷합니다. 내가 현재 얻을 수 있는 가장 큰 값은 무엇인지 체크해나가면 문제를 해결 할 수 있기 때문입니다.

다이나믹프로그래밍에서는 top-down과 bottom-up 방식 두가지가 있습니다. 상황에 따라서 상향식과 하향식의 풀이가 적합한지 그때마다 다르기도 합니다.

점화식은 다음과 같습니다. dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익

max(p[i] + dp[t[i] + i]], max_value)가 된다. 이때 max_value는 뒤에서부터 계산할 때 현재까지의 최대 상담금액에 해당하는 변수다.

n = int(input())
t = [] #각 상담을 완료하는데 걸리는 시간
p = [] #각 상담을 완료했을 때 받을 수 있는 금액
dp  = [0]*(n+1) #dp를 위한 1차원 테이블 초기화 n+1한 이유는 마지막+1일까지 있을 수 있음
max_value = 0

for _ in range(n):
    x,y = map(int, input().split())
    t.append(x)
    p.append(y)

#리스트를 뒤에서부터 거꾸로 확인
for i in range(n-1,-1,-1):
    time = t[i] + i
    #상담이 기간 안에 끝나는 경우
    if time <= n:
        #점화식에 맞게, 현재까지의 최고 이익 계산
        dp[i] = max(p[i] + dp[time], max_value)
        max_value = dp[i]
    #상담이 기간을 벗어나는 경우
    else:
        dp[i] = max_value

print(max_value)

for문 부터 한번 보겠습니다. 리스트를 뒤에서 거꾸로 확인하다고 되어 있네요

range에서 (시작값,끝값,스텝)이라고 했는데

일단 마지막 날은 비교하지 않을 것이니 n-1에서 시작을 하고 끝값의 -1은 인덱싱의 마지막을 나타내는 -1이 아니라 그냥 숫자 -1까지 입니다.

오름차순으로 할때 [0:2]라고 하면 01이 출력되는 것 처럼 -1까지로 지정을 하면 0까지 출력을 하게 되고 스텝은 역순으로 -1씩 하는 것입니다.

일단 첫번째로 6이 들어오고 t[6]번째에서 걸리는 시간은 2가 됩니다. 6+2 >= 7 로 불가능하니 max_value를 0으로 리턴하고 넘어가고 이는 5일때도 5+4>=7이 됩니다.

인덱스가 4일때(5일차) 5+2>=7 드디어 허용범위를 찾았습니다. 이때 아직 dp테이블에는 아무것도 없으니 최대값을 15로 넣고 dp테이블에 넣어줍니다.

이렇게 모든 테이블을 순회를 하면 가장 많은 값을 구할 수 있습니다.