[14501] 퇴사 - python 풀이

알고리즘 설계 기법

• Dynamic Programming
• 중복 호출을 해결하기 위해 메모리에 결과값을 저장하고, 다음 호출 때 해당 값을 사용(배열 사용)

경우가 무지무지 많으면서도 조건에 부합하는지 살펴야 한다.

0) n일에 예약된 상담을 할지 말지 따지면서도,
상담을 진행할 경우
1) 퇴사 전에 상담이 마무리되어야 하고
2) 해당 상담을 진행하는 동안 다른 상담은 진행할 수 없으므로, 이전에 진행중인 상담이 있었는지 확인해야 한다.

 

나는 2번 조건이 너무 까다로워서 애를 먹었는데, 이걸 해결하는 방법은 스케줄을 뒤에서부터 잡는 것이다.

뒤에서부터 일정을 잡을 경우, 앞 날에는 일정이 없으므로 2번 조건을 따지지 않아도 되는 것이다.

앞에서부터 일정 잡느라 끙끙댄 사람 접니다

 

문제를 보면

	1일	2일	3일	4일	5일	6일	7일
T	3	5	1	1	2	4	2
P	10	20	10	20	15	40	200

뒤에서부터 가능한 최대치로 일정을 잡으며, 앞으로 오는 방식이다.

7일(불가능)	0	0	0	0	0	0	0
6일(불가능)	0	0	0	0	0	0	0
5일	0	0	0	0	15+0 = 15	0	0
4일	0	0	0	20+15 = 35	15	0	0
3일	0	0	10+35 = 45	35	15	0	0
2일	0	20+0 = 20	45	35	15	0	0
1일	10+35 = 45	20	45	35	15	0	0

하지만 우리는 잡을 수 있는 모든 일정의 경우를 따지는 게 아니라 최대 소득 금액만 얻으면 되니까, 앞으로 오면서 최대값만 가지고 오면 된다.

2일

0

20+0 = 20

45

35

15

0

0

2일의 경우를 보자. 조건 1에 위배되지 않으므로, 상담을 할 수는 있다. 하지만 그렇게 되면 5일이라는 시간이 소요되기 때문에 최종 소득은 [2일차 소득 + 7일차 소득]이 된다.

하지만 해당 소득은 이전에 계산된 [3일차 소득 + 4일차 소득 + 5일차 소득]보다 적기 때문에 최대값이 아니다. 따라서 이 값은 무시해도 된다.

result[i] = max( P[i] + result[i + T[i]], result[i + 1] )

 

답

n = int(input())

t_list = []
p_list = []
answer = [0] * (n + 1)

for i in range(n):
    t, p = map(int, input().split())
    t_list.append(t)
    p_list.append(p)

for i in range(n - 1, -1, -1): #n일부터 1일까지 거꾸로 진행
    if t_list[i] + i > n: #상담 마감일이 퇴사일을 넘어가버리면
        answer[i] = answer[i + 1] #해당 상담을 하지 않으므로 금액 변동 없음
    else:
        #[현재 일을 맡았을 때 들어오는 돈 + 현재 일 끝난 뒤에 내가 계산해놨던 금액] VS 그냥 직전 금액
        answer[i] = max(p_list[i] + answer[i + t_list[i]], answer[i + 1])
print(answer[0])

문제 풀러가기

14501번: 퇴사

해답을 얻은 곳: https://gudwns1243.tistory.com/58