Create 12865.cpp

encrypted-def · web-flow · commit 2a244a7532b4 · 2025-03-29T00:01:23.000+09:00
diff --git a/Appendix E/12865.cpp b/Appendix E/12865.cpp
@@ -0,0 +1,31 @@
+// http://boj.kr/485b69efb085449ca4c64d848656498b
+#include <bits/stdc++.h>
+using namespace std;
+
+int n, k;
+int d[102][100002];
+int w[102];
+int v[102];
+
+int main(void) {
+  ios::sync_with_stdio(0);
+  cin.tie(0);
+
+  cin >> n >> k;
+  for(int i = 0; i < n; i++)
+    cin >> w[i] >> v[i];
+  
+  for(int i = 0; i < n; i++){
+    for(int j = 1; j <= k; j++){
+      if(i-1 >= 0)
+        d[i][j] = d[i-1][j];
+      if(j-w[i] >= 0){
+        if(i-1 >= 0)
+          d[i][j] = max(d[i][j], d[i-1][j-w[i]] + v[i]);
+        else
+          d[i][j] = v[i];
+      }
+    }
+  }
+  cout << d[n-1][k];
+}
