[BOJ] 백준 1535 - 안녕 풀이

1. 문제

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

1535번: 안녕

 

2. 풀이

베낭 알고리즘 문제이다.
물건의 개수가 사람의 수가 되었고, 가방의 무게 제한 대신 체력이 존재한다.
처음에 문제를 해결할 때는 체력 제한을 조건문으로 판별하려다 실패했고, 다른 분의 풀이를 참고하여 문제를 해결했다.

2중 반복문으로 탐색을 진행하는데, health_arr의 인덱스보다 크거나 같을 때까지 탐색을 진행하는 것이 포인트이다.
이렇게 탐색하면 선택된 인덱스의 체력보다 크거나 같을 때까지 탐색하기 때문에 체력이 0이 되거나 음수가 되는 경우는 없다.

 

3. 소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] health_arr = new int[N];
        int[] happy_arr = new int[N];

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

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

        int[] dp = new int[100];
        for (int i = 0; i < N; i++) {
            for (int j = 99; j >= health_arr[i]; j--) {
                dp[j] = Math.max(dp[j - health_arr[i]] + happy_arr[i], dp[j]);
            }
        }

        bw.write(dp[99] + "");
        bw.flush();
        bw.close();
        br.close();
    }
}