[백준] 1535번 : 안녕 – JAVA [자바]

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

1535번: 안녕

 

---

• 문제

 

 

---

• 문제 풀이

백준 1535번 안녕은 DP, 그중에서도 배낭 문제와 되게 유사한 문제이다. 배낭 문제를 아직 잘 모르면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/50

[알고리즘] 배낭 문제 (Knapsack Problem)

 

보통 배낭 문제에서는 물건의 개수 n이 있고, 배낭의 무게 제한 k가 있다. 그리고 물건들의 무게들인 배열 w가 있고 이 물건들의 가치인 배열 v가 있다. 이번 문제도 똑같다.

 

물건의 개수 대신 사람 n명이 있고 무게 제한 대신 체력이 있다. 단, 여기서 최대 체력이 문제에서 100이라고 주어져서 100이라고 생각을 할 수도 있는데 실은 99이다. 왜냐하면 체력이 0이 되거나 음수가 되면 세준이가 죽어서 기쁨을 못 느낀다고 문제에 나와있기 때문이다. 그리고 다른 배낭 문제들과 같게 입력에서 각 사람을 만날 때마다 소요하는 체력들이 주어지고 그 사람들을 만날 때 얻는 기쁨들이 주어진다. 이 점만 참고하면 배낭 문제와 똑같기 때문에 쉽게 해결할 수 있을 것이다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int k = 99;
        int[][] dp = new int[n+1][k+1];
        int[] w = new int[n+1];
        int[] v = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st2.nextToken());
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (w[i] <= j) {
                    dp[i][j] = Math.max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.print(dp[n][k]);
    }
}

 

---

• 후기

이 문제는 배낭 문제 코드에서 살짝만 변형하면 풀 수 있는 문제였다.