[백준(BOJ)] 1535번: 안녕 (C++)

배낭문제와 다이나믹 프로그래밍(DP)으로 생각하고 코드를 구현했다.

처음에 인사할 때 잃는 체력과 얻는 기쁨을 pair로 vector에 저장하고 남은 체력마다의 최대 기쁨도 vector에 저장했는데, 이때 vector에서 가져오고 저장하고 이런 처리하는 속도가 배열과 비교했을 때 상대적으로 너무 오래 걸리는 것 같았다. 

그래서 잃는 체력과 얻는 기쁨은 1차원 배열에, 사람마다 남은 체력이 있을 때의 값을 최대 기쁨으로 저장하는 2차원 배열 DP를 이용해서 배낭 문제의 개념으로 문제를 풀었다.

 

인사하는 사람마다 남은 체력이 1~100일 때 인사했을 때 남은 체력이 0보다 크고 얻는 기쁨이 최대이면 이를 취하고, 그렇지 않으면 이전 사람에서의 해당 체력일 때를 취하였다. 

처음에는 2차원 배열로 최대 기쁨을 구하는 방법을 생각했고, 다음으로 1차원 배열을 사용하는 방법을 구현해보았다.

 

#include <iostream>
using namespace std;

int main(){
    int N; // N: 세준이를 생각해준 사람 수
    int DP[21][101]={0,}; // DP[사람 순서][남은 체력] = 최대 기쁨
    int H[21];
    int J[21];

    scanf("%d", &N);

    for(int i=1; i<=N; i++) // 각각의 사람에게 인사를 할 때, 잃는 체력 순서대로 입력
        scanf("%d", &H[i]);
    
    for(int i=1; i<=N; i++) // 각각의 사람에게 인사를 할 때, 얻는 기쁨 순서대로 입력
        scanf("%d", &J[i]);

    
    for(int i=1; i<=N; i++){

        for(int j=1; j<=100; j++){
            if(j-H[i] > 0)
                DP[i][j] = max(DP[i-1][j], DP[i-1][j-H[i]] + J[i]);
            else DP[i][j] = DP[i-1][j];
        }
        
    }
    
    printf("%d\n", DP[N][100]);

    return 0;
}

#include <iostream>
using namespace std;

int main(){
    int N; // N: 세준이를 생각해준 사람 수
    int DP[101]={0,}; // DP[남은 체력] = 최대 기쁨
    int H[21];
    int J[21];

    scanf("%d", &N);

    for(int i=1; i<=N; i++) // 각각의 사람에게 인사를 할 때, 잃는 체력 순서대로 입력
        scanf("%d", &H[i]);
    
    for(int i=1; i<=N; i++) // 각각의 사람에게 인사를 할 때, 얻는 기쁨 순서대로 입력
        scanf("%d", &J[i]);

    for(int i=1; i<=N; i++){

        for(int j=100; j>H[i]; j--){
            DP[j] = max(DP[j], DP[j-H[i]] + J[i]);
        }
    }


    printf("%d\n", DP[100]);

    return 0;
}