[백준 1535] 안녕

얘도 dp문제임

01 배낭문제인 평범한 배낭 이 문제랑 똑같은 상황임

 

얘도 가치있는거부터 넣는다고 좋은게 절대 아님

greedy로 안풀림

 

greedy로 풀었을때의 반례를 보자면

총 10 담을 수 있는데

8 8

5 5

4 4

 

이렇게 있으면 5 4 조합 넣는게 훨씬 이득임

하지만 greedy로 풀면 8에서 끝남

그래서 dp로 풀어야함

greedy가 안먹히기 때문

 

---

#include <iostream>
#define SIZE 21

using namespace std;

int N;
int L[SIZE], J[SIZE];
int dp[SIZE][101];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> L[i]; // 체력
	for (int i = 1; i <= N; i++) cin >> J[i]; // 기쁨

	for (int i = 1; i <= N; i++) {
		for (int HP = 1; HP <= 100; HP++) {
			
			// 인사할 수 있으면
			if (HP - L[i] > 0) {
				dp[i][HP] = max(dp[i - 1][HP], dp[i - 1][HP - L[i]] + J[i]);
			}
			// 인사 못하면
			else {
				dp[i][HP] = dp[i - 1][HP];
			}
		}
	}
	cout << dp[N][100];
	return 0;
}