BAEKJOON : 14501

No. 14501

import sys

n = int(sys.stdin.readline())
T = [0]
P = [0]
dp = [0] * (n+1)

for _ in range(n):
    t,p = map(int, sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

for day in range(1,n+1):
    temp = 0
    if T[day] > 1:
        for i in range(day-1,-1,-1):    
            if T[i] == day-i+1:
                temp = dp[i] + P[i]
            dp[day] = max(dp[day], dp[day-1], temp)
    else:
        for i in range(day-1,-1,-1):
            if T[i] == day-i+1:
                temp = dp[i] + P[i]
            dp[day] = max(dp[day], dp[day-1] + P[day], temp)
    
print(dp[n])

import sys

n = int(sys.stdin.readline())
T = [0]
P = [0]
dp = [0] * (n+1)

for _ in range(n):
    t,p = map(int, sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

# 초기값 설정
if T[n] == 1:
    dp[n] = P[n]

for day in range(n-1,0,-1):
   
    # day에 상담하면 퇴사일을 넘어가는 경우
    if day+T[day]-1 > n:
        dp[day] = dp[day+1]
    
    # day에 상담을 하는 경우와, 하지 않고 다음 day로 넘어가는 경우중 큰 값
    else:
        if day+T[day]-1 == n:      # day 기준으로 T[day]만큼 일하면 마지막 날인 경우
            work = 0
        else:
            work = dp[day+T[day]]
        dp[day] = max(dp[day+1], work + P[day])

print(dp[1])

import sys

def dfs(day,sum):
    global res
    flag = False

    if day+T[day]-1 <= n:           # 해당 day에 일을 해도 퇴사일을 넘지 않으므로 일을 하는 경우
        sum += P[day]               # 일을 했으니 돈을 받음
        flag = True

        if day+T[day] <= n:         # 그 뒤로 날이 남아있는 경우 
            dfs(day+T[day], sum)        
        
        res = max(res,sum)

    if flag == True:            # 일하는 경우를 dfs 로 체크했다면 안하는 경우를 위해 다시 -
        sum -= P[day]     

    if day+1 <= n:              # 해당 day에 일을 안하는 경우 
        dfs(day+1, sum)
    
    
n = int(sys.stdin.readline())
T = [0] 
P = [0]
res = 0

for _ in range(n):
    t,p = map(int,sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

dfs(1,0)
print(res)

import sys
import math

def dfs(day):
    
    # 정확히 마지막 날의 경우
    if day-1 == n:      
        return 0

    # 퇴사일을 넘어가는 경우
    elif day > n:
        return -math.inf
    
    # day를 기준으로 일을 하지 않고 바로 다음날로 가거나, 일을 하고 일한 날짜만큼 뒤로 가거나
    return max(dfs(day+1), dfs(day+T[day])+P[day])
    
    
n = int(sys.stdin.readline())
T = [0] 
P = [0]

for _ in range(n):
    t,p = map(int,sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

print(dfs(1))

import sys
import math

def dfs(day):

    # 정확히 마지막 날의 경우
    if day-1 == n:      
        return 0

    # 퇴사일을 넘어가는 경우
    elif day > n:
        return -math.inf
    
    if dp[day] != -1:
        return dp[day]
    
    # day를 기준으로 일을 하지 않고 바로 다음날로 가거나, 일을 하고 일한 날짜만큼 뒤로 가거나
    dp[day] = max(dfs(day+1), dfs(day+T[day])+P[day])
    print(dfs(day+1), dfs(day+T[day])+P[day])
    return dp[day]
    
n = int(sys.stdin.readline())
T = [0] 
P = [0]
dp = [-1] * (n+1)

for _ in range(n):
    t,p = map(int,sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

print(dfs(1))