[BOJ] 1535 안녕

#include <iostream>
#define MAXL 20
#define MAXJ 100

using namespace std;
int DP[MAXL+1][MAXJ+1], L[MAXL+1], J[MAXJ+1];
int N;

void input() {
	cin >> N ;

	for (int i = 1; i <= N; i++)  
		cin >> L[i];  
	for (int i = 1; i <= N; i++)  
		cin >> J[i]; 



}
void solve() {

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j < 100; j++) {
			if (j >= L[i])
				DP[i][j] = max(DP[i - 1][j - L[i]] + J[i], DP[i - 1][j]);
			else
				DP[i][j] = DP[i - 1][j];
		}
	}
	int res = 0;
	for (int i = 1; i < 100; i++)
		res = max(DP[N][i], res);
	cout << res << endl;

	//cout << DP[N][99] << endl;
}

int main() {

	input();
	solve();
}

가방 문제였다.

우선 초기화를 안해줘도 되는데 해준 부분이 가장 문제였다.

시작을 1부터로 해야 -1을 해줬을 때 문제가 없다.

정답

 

 

 

[백준 1535번] 안녕

 

 

 

가방 문제

가방 문제

 

 

 

 

 

[알고리즘] 배낭 문제(Knapsack Problem)