[DP] 1535번 안녕

1535번 안녕

 

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

 

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력

3
1 21 79
20 30 25

 

예제 출력

50

 

해결방법

Knapsack Problem 을 적용한 DP 문제이다

이런 유형을 처음 접한 터라 정말 너~~~무 어려웠다....

 

 

⭐️ 솔루션 ⭐️

• 1번째 사람만 인사하는 경우, 체력 1~100 까지의 최대 기쁨을 구한다
• 1~2번째 사람까지 인사하는 경우, 체력 1~100 까지의 최대 기쁨을 갱신한다
• 1~n번째 사람까지 인사하는 경우, 체력 1~100 까지의 최대 기쁨을 갱신한다

 

점화식은 아래와 같다

D(i,k) =  { D(i-1,k) (lose[i] > k)
    	  { max(D(i-1,k), D(i-1,k-lose[i] + joy[i] (lose[i] ≤ k))

 

또한 한명의 사람하고는 한번밖에 인사를 하지 못한다는 조건을 구현하기 위해 1차원 배열, 2차원 배열로 각각 구현하였다

 

 

 

소스코드

1차원 배열을 사용한 소스코드

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int n;
int d[101];
int lose[21];
int joy[21];

void dp(){
    for(int i=1; i<=n; i++){
        for(int j=100; j>lose[i]; j--){
            d[j] = max(d[j], d[j-lose[i]] + joy[i]);
        }
    }
    
    cout << d[100] << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> lose[i];
    }
    
    for(int i=1; i<=n; i++){
        cin >> joy[i];
    }
    
    dp();
    
    return 0;
}

 

2차원 배열을 사용한 소스코드

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int n;
int d[21][101];
int lose[21];
int joy[21];

void dp(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=100; j++){
            if(lose[i] >= j){
                d[i][j] = d[i-1][j];
            }else{
                d[i][j] = max(d[i-1][j], d[i-1][j-lose[i]] + joy[i]);
            }
        }
    
    }
    
    cout << d[n][100] << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> lose[i];
    }
    
    for(int i=1; i<=n; i++){
        cin >> joy[i];
    }
    
    dp();
    
    return 0;
}