14501번 퇴사

문제 출처 : https://www.acmicpc.net/problem/14501

나도 그만두고 싶다ㅏ..아나ㅏ아..

사고과정

최댓값 관련한 문제는 역시 DP인가?
처음 문제를 접했을 때는 T와 P라는 두 가지 조건에 따라 문제가 해결되므로 예전에 풀어본(?) K-N냅색 문제와 같이 이차원 DP를 이용하여 문제를 푸는 건가 생각했다. 하지만 2차원 배열에 어떻게 적용해야 할지 몰라서 갈피를 잡지 못하고 이건 아닌가보다 싶었다. 단순히 직전의 요소로만 현재의 DP가 결정되지 않고 이전 모든 DP들을 대상으로 고려해봐야 한다. 이전의 요소들 중 한 개의 요소만을 이용해서 현재의 DP를 결정한다면 뒤에 값들은 어떻게 결정해야 하는가? ( 현재 i번째 요소를 포함할지 포함하지 않을지 이런 걸 어떻게 결정해줘야하지? = "미결정성" )

다시 직관적으로 생각해보자. 결국 문제에서 구하고자 하는 것은 수익의 최댓값

점진적으로 수익의 최댓값이 커지는 게 아니므로 모든 요소에서의 최댓값을 알아야 하고 그 중에서 가장 큰 이익을 선택해야 한다.

그렇다면 현재에 집중하자. i번째에서 수익이 최대가 될려면 이전의 모든 수익 중에서 가장 큰 수익을 넘겨받아야 한다. 그런데 이때 T라는 조건때문에 이전 모든 수익이 조사대상이 될수 없기에 내가 넘겨받을 수 있는 수익,날들을 can이라는 list에 담고 그 중, 내가 가능한 날들 중에서 가장 큰 수익이 날때를 넘겨받는다.

마지막으로 한 가지 조건이 추가로 붙는다면 만약 i번째 할 상담의 날이 퇴사를 하기 전까지 끝나지 않는다면 상담을 할 수 없으므로 i번째 수익을 더해주지 않는다. ( 그렇지 않다면, 퇴사하기 전에 상담이 끝난다면 더해준다. 왜? 상담을 하면 수익이 늘어나니까 )

import sys

N = int(sys.stdin.readline().rstrip("\n"))
dp = [0 for _ in range(N)]
T_P = [list(map(int,sys.stdin.readline().rstrip("\n").split())) for _ in range(N)]

for i in range(N) :
    can = [0]
    for j in range(i) :
        if i-j >= T_P[j][0] :
            can.append(dp[j])
    dp[i]=max(can)
    if N-i >= T_P[i][0] :
        dp[i]+=T_P[i][1]
print(max(dp))

2차원 DP 문제를 다시 살펴볼 필요가 있겠군