[인프런] 최대점수 구하기

---

문제설명

이번 정보올림피아드 대회에서 좋은 성적을 내기 위해 현수는 선생님이 주신 N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는 데 걸리는 시간이 주어지게 된다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 한다.(해당 문제는 해당 시간이 걸리면 푸는 걸로 간주한다. 단, 한 유형당 한 개만 풀 수 있다.)

입력조건

• 첫 줄에 문제 개수 N(1 <= N <= 100)과 제한시간 M(10 <= M <= 1000)이 주어진다.
• 둘째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는 데 걸리는 시간이 주어진다.

출력조건

• 첫줄에 제한 시간 안에 얻을 수 있는 최대 점수를 출력한다.

사고과정

• 냅색알고리즘을 이용해야 하긴 하는데... 이번엔 중복을 허용하지 않고 한개씩만 사용해야 하는 문제였다. 기존에 풀었던 방식으로 구현하려니 답이 틀리게 나왔다..
• 도저히 몰라서 강의를 보게 되었고 처음에 2차원 DP 테이블을 정의해서 구현하는 방식을 알려주었다. 그런데 이는 DP 문제 특성 상 데이터 범위가 커지게 되면 공간복잡도가 매우 커져 문제가 발생하게 된다.. 그래서 1차원 DP 테이블로 해결하는 방법을 알려주었는데, 기존에는 앞에서부터 뒤로 전진하면서 DP 테이블을 갱신해서 중복을 허용했지만 중복을 허용하지 않게 하려면 뒤에서부터 앞으로 가는 방향으로 DP 테이블을 갱신해주면 되었다..!! 이거는 따로 깃헙에다가도 기록해놓아야 할 듯하다.. 

풀이(스스로 못 푼 풀이)

n, m = map(int, input().split())
# 앞에서부터 전진하면 중복이 무조건 되기 떄문에 거꾸로 DP 테이블 갱신!
dp = [0] * (m+1)
for _ in range(n):
    score, time = map(int, input().split())
    for j in range(m, time-1, -1):
        dp[j] = max(dp[j], dp[j - time] + score)
print(dp[m])