생성일: 2022년 2월 26일 오후 4:50
# 최대점수 구하기(냅색 알고리즘) with 2차원 배열
import sys
sys.stdin = open("input.txt", "rt")
if __name__ == "__main__":
n, m = map(int, input().split())
dy = [[0 for _ in range(m+1)] for _ in range(n+1)]
# dy[i][j]는 i번째 문제까지 고려하고 j시간이 주어졌을 때 최대 점수
for i in range(1, n+1):
score, time = map(int, input().split())
for j in range(time, m+1):
dy[i][j] = max(dy[i-1][j], dy[i-1][j-time]+score)
print(dy[n][m])
이전의 냅색 문제와의 차이점 ⇒ 중복 선택 불가능 ⇒ 이차원 배열을 만들어서 해결해야함 (값을 중복해서 덮어 쓸 수 없기 때문)
중복 선택이 없어야 하기 때문에 dy[i][j-time]과 비교하는 것이 아니라 이전에 입력받은 문제를 기준으로 비교해야 한다. ⇒ dy[i-1][j-time]과 비교
위와 같이 이차원 배열을 만들어서 문제를 푸는것이 정석이지만, 실전에서 공간복잡도가 매우 증가하는 문제가 있기 때문에 일차원 배열로 간소화하여 푸는 방법도 존재한다.
# 최대점수 구하기(냅색 알고리즘) with 1차원 배열
import sys
sys.stdin = open("input.txt", "rt")
if __name__ == "__main__":
n, m = map(int, input().split())
dy = [0 for _ in range(m+1)]
# dy[j]는 j시간이 주어졌을 때 최대 점수
for i in range(0, n):
score, time = map(int, input().split())
for j in range(m, time-1, -1):
dy[j] = max(dy[j], dy[j-time]+score)
print(dy[m])