[백준 15486] 퇴사 2

https://www.acmicpc.net/problem/15486 문제이해 N일동안 상담을해서 얻을 수 있는 최대 수익을 구해라. 풀이 DFS로 접근하기에는 N이 최대 1,500,000으로 depth 제한이나 시간 초과가 발생할 확률이 높아서 DP를 고민했다.

DP도 첫날부터 계산할지 마지막 날부터 계산할지 계속 고민을 하다 첫날부터 계산하기로 하고 풀었다. 코드 from sys import stdin N = int(stdin.readline()) T=[0]*(N+1) P=[0]*(N+1) dp = [0]*(N+1) for i in range(N): t, p = map(int, stdin.readline().split()) T[i+1] = t P[i+1] = p for i in range(1, N+1): dp[i] = max(dp[i], dp[i-1]) if i + T[i] - 1 <= N: # 퇴사 전에 상담 완료 가능하면 dp[i + T[i] - 1] = max(dp[i + T...