[BOJ/Python] 백준 14501번 - 퇴사

백준 #14501 퇴사

14501번: 퇴사

 

수요일 모각코 때 못 풀었던 문제 !! 드디어 풀었다 !!

 

N = int(input())    # 퇴사일
T = []  # 상담을 완료하는데 걸리는 기간
P = []  # 상담을 했을 때 받을 수 있는 금액
for i in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)

profit = [0 for i in range(N+1)]  # 최대 이익

for i in range(N-1, -1, -1):
    if i == N-1 and i+T[i] == N:    # 마지막 날 상담 기간이 1일이어서 상담이 가능한 경우
        profit[i] = P[i]
    elif i+T[i] <= N:  
        profit[i] = max(P[i]+profit[i+T[i]], profit[i+1])
    else:   # 상담 기간이 퇴사일을 넘어갈 경우 (i일 날 상담 못 함)
        profit[i] = profit[i+1]

print(profit[0])

 

 

수요일에 짰던 알고리즘은 완전 잘못됐다. 처음 세운 재귀식부터 잘못되어서 나름 dp형태로 바꾼 것도 잘못될 수밖에 없었다. T[i]를 타고 가는 재귀식은 T[i]번째 날 상담을 안 하고, T[i]번째 날 이후에 상담을 하는 경우는 따지지 않고 있어서 최대 이익을 구할 수가 없다. 그러니까, 만약 첫 번째 날 일을 할 경우 1 > T[1] > T[T[1]] ... 이 루트로 이동해 무조건 "T[i]"날 상담을 하는 경우만 따지고 있었다. 하지만 1일날 상담을 하고 T[1+@] 날 상담을 할 수도 있다. T[i] 날 이전에만 상담을 못 하는 거지 T[i] 날 이후에는 상담을 할 수 있다.

 

사실 처음 문제를 접했을 때 dp형태로 i번째 날 상담을 하는 경우 / i 번째 날 상담을 하지 않는 경우로 나누어 푸는 방법을 제일 먼저 떠올리긴 했다. 하지만 식으로 구현이 잘 안 돼서 다른 방법을 떠올린 건데, 결과적으로 처음 생각한 대로 푸는 게 맞았다. for문을 거꾸로 돌리기만 하면 됐다. i번째 날부터 N일까지가 아닌, 거꾸로 N일부터 i번째 날까지 상담했을 때 최대 이익을 구해나가는 것이다. 당일날 상담을 할 경우와 당일날 상담을 하지 않는 경우를 비교해 더 큰 이익을 구해준다. 만약 i번째 날 상담을 하는 것보다 i번째 날 상담을 하지 않고 i번째 날 이후에 상담했을 때의 이익이 더 크다면 그것을 택하게 되는 것이다. i번째 날 이후에 상담했을 때의 이익은 바로 이전에 구한 이익이 된다. 최대 이익을 계속 구해온 것이기 때문에 이전에 구한 이익엔 그 날까지의 최대 이익이 구해져 있다. 그래서 결국 i+1번째 날의 이익과 비교하는 것이다. (for문을 거꾸로 돌리고 있기 때문에 이전은 i+1)

 

크게 세 가지로 구분해 i번째 날까지 상담했을 때의 최대이익을 구했다.

1. N일날 상담 기간이 1일이어서 상담을 할 수 있는 경우, 그때 최대 이익은 P[N]이 된다.

2. i번째 날 상담 기간이 N일을 넘어가지 않아 상담이 가능할 때 (i+T[i] <= N), 그날 상담을 할 경우와 상담을 하지 않았을 경우를 비교해 더 큰 이익을 구해준다.

3. 상담 기간이 N일을 넘어갈 경우, 그날 상담을 할 수 없기 때문에 i+1번째 날의 이익이 그대로 오게 된다.

 

마지막으로 첫 번째 날까지의 이익을 구해주면 최종적으로 첫 번째 값에 첫 날부터 N일까지 상담했을 때의 최대 이익이 구해지게 된다.

 

 

꽤나 오래 걸렸는데, 풀고나니 조금 아쉬웠다 ㅜ 이런 건 바로바로 풀어줘야 되는데 ...

 

그리고 예제 2번에서 마지막 날 1일 걸리는 상담을 어떻게 하냐고 했었는데 ,, 당연히 할 수 있다. 당일날 해서 당일날 끝나는 상담인 건데 1일 걸린다고 하니까 당일날 시작해서 다음 날 끝나는 걸로 착각했다. 바보야 !!