퇴사

풀이

 문제의 조건에서 n의 범위(1<=n<=15)가 작으므로 완전 탐색으로도 풀수 있다. 하지만 DP가 시간복잡도 측면에서 효율적이라고 생각해서 DP로 풀었다.
 입력으로 주어진 data 리스트에는 각 날짜에 대한 상담 시간과 보수가 포함되어 있다. 각 날짜마다 가능한 상담 일정의 경우를 고려하여 최대 이익을 갱신하면 된다. dp[i]는 i번째 날까지의 최대 이익을 의미한다. i + t - 1 <= n 조건을 통해 현재 날짜에서 상담 시간을 더한 값이 전체 날짜를 넘지 않을 경우에만 상담을 진행하면서 해당 날짜의 최대 이익을 갱신하면 된다. i번째 날에 상담을 진행하지 않는 경우(dp[i] < dp[i-1])에도 이전 날짜의 최대 이익을 그대로 가져와서 갱신한다.

n = int(input())

data = []
for _ in range(n):
    data.append(list(map(int, input().split())))

dp = [0 for _ in range(n+1)]

for i in range(1, n+1):
    t = data[i-1][0]
    p = data[i-1][1]
    if i + t -1 <= n:
        dp[i+t-1] = max(dp[i+t-1], dp[i-1] + p)
    
    # i번째 날에 상담 진행 X    
    if dp[i] < dp[i-1]:
        dp[i] = dp[i-1]
print(dp[n])

시간복잡도 : O(n)