100번 최대 점수 구하기(냅색 알고리즘) 수강 완료

Joseph-Cha · Joseph-Cha · commit e74f45e3447a · 2022-08-24T23:19:27.000+09:00
diff --git a/인프런_알고리즘_강의/김태원/섹션 5. Dynamic programming(동적계획법)/100. 최대점수 구하기(냅색 알고리즘).md b/인프런_알고리즘_강의/김태원/섹션 5. Dynamic programming(동적계획법)/100. 최대점수 구하기(냅색 알고리즘).md
@@ -22,8 +22,36 @@
 ### 출력 예제
 41
 
-
 ### 모범 답안
 ``` Cpp
+#include <iostream>
+#include <fstream>
+#include <vector>
+#include <algorithm>
+using namespace std;
+int main() {
+    ios_base::sync_with_stdio(false);
+    ifstream cin;
+    cin.open("input.txt");
+    // ps: 풀이 점수
+    // pt: 풀이 시간
+    int n = 0, m = 0, ps = 0, pt = 0;
+    cin >> n >> m;
+    vector<int> dy(m + 1);
+    for (int i = 0; i < n; i++) {
+        cin >> ps >> pt;
+        // j: 현재 주어진 시간
+        for (int j = m; j >= pt; j--) {
+            // 현재 주어진 시간에 얻을 수 있는 최대 점수
+            // vs
+            // 다음 문제를 풀었을 때 얻을 수 있는 최대 점수를 합친 값
+            dy[j] = max(dy[j], dy[j - pt] + ps);
+        }
+    }
+    cout << dy[m];
+    return 0;
+}
+// dy[j]의 의미
+// j만큼의 시간이 주어졌을 때 얻을 수 있는 최대 점수
 
 ```
