[백준 2024/10/09] 14501번 퇴사

1. 문제

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

 

2. 접근 방법

이번 문제는 dp를 이용한 문제이다.

이는 해당 Ti로부터 뒤에 값이 이용 불가해 지기 때문에, 뒤에서 부터 계산을 하는 것이 편리할 것이라는 생각이 들었다.

 

즉, 6일 -> 5일 -> 4일 ... 순으로 탐색을 진행할 것이다.

 

dp에 저장되는 값들은 해당 일에서의 최대 이익을 뜻하게 된다.

 

1. 현재 값 추가 < 이전 값 적용

현재 값을 추가할 때보다 이전 값을 적용시켰을 때, 더 이득일 때가 있다.

1일을 예로 들어보자. 

1일의 상담을 받게 된다면, 1일에서 5일 뒤부터 상담이 가능해 진다. 즉, 6일부터 상담이 가능해 진다.

하지만 6일 일 때의 최대 이익인 dp[i + counsle[i][0]] 은 0이다. 6일을 선택해서 얻을 수 있는 이익 0과 1일을 선택해서 얻을 수 있는 이익인 p1 (20)의 합은 20이다. 반면, 1일을 선택하지 않았을 때의 dp[i+1] 즉, 2일의 값은 45이므로 1일을 선택하지 않는 선택을 하게 된다.

이에 dp[i] = dp[i+1]을 적용시키게 된다.

 

3. 코드

def get_max_profit(counsle, n):
    dp = [0] * (n+1)

    for i in range(n-1, -1, -1):
        if i + counsle[i][0] > n:
            dp[i] = dp[i+1]
            continue
        if dp[i + counsle[i][0]] + counsle[i][1] > dp[i+1]:
            dp[i] = dp[i + counsle[i][0]] + counsle[i][1]
        else:
            dp[i] = dp[i+1]
    return dp[0]


if __name__ == "__main__":
    n = int(input())
    counsle = [[0, 0] for _ in range(n)]

    for i in range(n):
        t, p = map(int, input().split())
        counsle[i][0] = t
        counsle[i][1] = p

    print(get_max_profit(counsle, n))