[PS] 백준1535 : 안녕(Java)

문제

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

1535번: 안녕

---

풀이

부분집합으로 풀이가 가능한 문제
DP Knapsack으로 접근해봤던 문제임

접근법

Knapsack으로 풀어보자고 권유를 받아 DP 상향식으로 접근

세준이의 최대체력은 100으로 각 체력을 행으로 주어지는 사람을 열로 2차원 dp배열을 초기화

각 j번째 사람에 대해 hp[j]가 현재 체력 i보다 낮을 경우 이전 부분문제의 해와 비교하여 최대값을 갱신

누적값이 필요하기 때문에 체력 i보다 크다면 이전 부분문제의 해로 값 삽입

 

---

소스코드

import java.io.*;
import java.util.*;

//BOJ_1535 안녕
public class Main {
    static int N;
    static int[] hp, happy;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine()); //사람 수

        hp = new int[N+1];
        happy = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            hp[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            happy[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[101][N+1];

        for(int i=1; i<101; i++) { //체력에 대해서
            for(int j=1; j<=N; j++) { //각 사람들을 탐색
                if(i > hp[j]) { //인사 가능할 때
                    dp[i][j] = Math.max(dp[i][j-1] , dp[i-hp[j]][j-1] + happy[j]);
                }
                else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }

        System.out.println(dp[100][N]);

    }
}

 

---

정리

평범한 배낭 2를 풀면서 Knapsack에 대한 정리도 할 겸 간단한 부분집합 문제를 Knapsack으로 접근해보았음

 

dp문제가 아니라도 dp로 접근해본 적은 이번이 처음인데 되게 흥미롭고 일반적인 풀이보다 확실히 dp로 접근했을 때 시간복잡도가 현저히 낮게 나온다는 점을 확인할 수 있었음!

 

앞으로 꾸준하게 dp문제들을 풀어보면서 적응해야 할 것 같음.