[1535번] 안녕

문제링크 : https://www.acmicpc.net/problem/1535

 

 

1. 문제 인식

사람 N명에게 인사를 할 수 있다.

인사하면 hp[i]만큼 체력을 잃고 happy[i]만큼 기쁨을 얻는다.

체력이 0 이하가 되면 죽는다 (즉, 체력은 최소 1이어야 한다).

목표: 체력이 1 이상 남도록 하면서 얻을 수 있는 기쁨의 최대값 구하기.

 

즉, 각 사람에게 인사를 "할지 말지" 선택해야 함
→ 선택의 문제 → 부분 문제의 최적해 → 동적 계획법(DP) 를 사용하자

 

 

이 문제는 0/1 Knapsack 문제와 유사하다 

 

Knapsack 요소 이 문제의 대응 항목

무게 (비용)	체력 소모 (hp[i])
가치 (얻는 것)	기쁨 (happy[i])
최대 무게	체력 제한 (100 이하)

 

사람마다 한 번만 인사할 수 있으므로 0/1 Knapsack이다.

 

 

2. 상태 정의 (DP 배열 정의)

 

dp[i] = 체력이 i일 때 얻을 수 있는 최대 기쁨

인사를 해서 체력이 i가 됐을 때, 그때까지의 최대 기쁨을 저장

초기 상태: 아무것도 안 한 상태 → dp[100] = 0 (체력 100, 기쁨 0)

 

 

3. 점화식 설계

 

사람 i를 고려할 때:

현재 체력이 j일 때

그 사람에게 인사하면 hp[i]만큼 체력을 잃고, happy[i]를 얻는다.

체력이 0이 되면 죽으므로 → j - hp[i] > 0일 때만 인사 가능

 

for (int i = 0; i < N; i++) {
    for (int j = 100; j >= hp[i]; j--) {
        if (j - hp[i] > 0) { // 체력이 hp[i] 이상이어야 인사 가능
            dp[j] = Math.max(dp[j], dp[j - hp[i]] + happy[i]);
        }
    }
}

 

역순 순회하는 이유: 같은 i에 대해 중복 선택을 방지하기 위해 (0/1 Knapsack 특성)

 

 

4. 최종 결과 구하기

int max_happy = 0;
for (int i = 1; i <= 100; i++) {
    max_happy = Math.max(max_happy, dp[i]);
}

 

체력이 1 이상인 상태 중에서 가장 큰 기쁨값을 찾으면 된다.

 

 

5. 전체코드

 

package DynamicPrograming;

import java.util.Scanner;

public class _1535 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 사람 수
        int []hp = new int[N]; // 인사를 할 때 마다 잃는 체력
        int []happy = new int[N]; // 인사를 할 때마다 얻는 기쁨

        for (int i = 0; i < N; i++) {
            hp[i] = sc.nextInt();
        }

        for (int i = 0; i < N; i++) {
            happy[i] = sc.nextInt();
        }

        int[] dp = new int[101]; // 체력은 최대 100

        for (int i = 0; i < N; i++) {
            for (int j = 100; j >= hp[i]; j--) {
                if (j - hp[i] > 0) { // 체력이 hp[i] 이상이어야 인사 가능
                    dp[j] = Math.max(dp[j], dp[j - hp[i]] + happy[i]);
                }
            }
        }

        int max_happy = 0;
        for (int i = 1; i <= 100; i++) {
            max_happy = Math.max(max_happy, dp[i]);
        }

        System.out.println(max_happy);
    }
}