[BOJ] 1535. 안녕 (bruteforcing, dp, knapsack)

Silver II

https://www.acmicpc.net/problem/1535

1535번: 안녕

세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.

세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.

세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.

 

input:

• 첫째 줄에 사람의 수 N(≤ 20)이 들어온다.
• 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어온다.
• 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 사람부터 순서대로 들어온다.
• 체력과 기쁨은 100보다 작거나 같은 자연수 또는 0이다.

output:

• 첫째 줄에 세준이가 얻을 수 있는 최대 기쁨을 출력한다.

 

---

Idea :

• knapsack 문제
  • 제한된 체력 내에서 얻을 수 있는 최대 기쁨 구하기
    = 제한된 크기의 가방에 넣을 수 있는 보석의 최대 가치 구하기
• knapsack (dp)
  • dp[i][j] = i 번쩨 사람 까지 고려했을 때, j의 체력으로 얻을 수 있는 최대 기쁨의 크기 
  • 한 사람에 대해 2 가지 경우 가능
    1. 인사를 하지 않는 경우
       • 가지고 있는 체력으로 인사를 할 수 없거나
       • 인사를 하지 않았을 때 더 큰 기쁨을 얻을 수 있는 경우
    2. 인사를 하는 경우
       • 가지고 있는 체력으로 인사를 할 수 있고, 인사를 하는 것이 더 이득인 경우

Code :   

#include <iostream>

using namespace std;

#define MAX_L 100

int main() {
	// ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	int N;
	int L[21] = {}, J[21] = {};

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

	/* solve */
	int dp[21][MAX_L] = {};
	// dp[i][j] = i 번째 사람에게까지 인사할 수 있고, 체력이 j만큼 있다고 했을 때 얻을 수 있는 최대 기쁨
    
	for (int i=1; i<=N; i++) {
		for (int j=1; j<MAX_L; j++) {
			dp[i][j] = dp[i-1][j];
			if (j - L[i] >= 0)
				dp[i][j] = max(dp[i-1][j], dp[i-1][j - L[i]] + J[i]);
		}
	}

	/* print answer */
	cout << dp[N][MAX_L - 1] << "\n";
}

 

---

Result : 

메모리: 2020 KB,  시간: 0 ms

 

Review :