이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 0-1 배낭문제를 완전히 익히기 위해 연속해서 배낭 문제를 풀어보았다.

Code

n, t = map(int, input().split())
chapter = [()]
for _ in range(n):
    a, b = map(int, input().split())
    chapter.append((a, b))
dp = [[0 for _ in range(t+1)] for _ in range(n+1)]
answer = 0
for i in range(1, n+1):
    for j in range(1, t+1):
        if chapter[i][0] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(chapter[i][1]+dp[i-1][j-chapter[i][0]], dp[i-1][j])
        answer = max(answer, dp[i][j])
print(answer)