[백준] 1535: 안녕 - JAVA

 

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

 

풀이

DP, 배낭 문제.

인사를 할때마다 체력을 잃고 기쁨을 얻는다.

체력 100에서 시작해서 0이 되면 죽는다.

dp배열을 dp[사람의 수][100] 으로 설정했다.

사람마다 잃는 체력, 얻는 기쁨을 통해 이전 dp배열과 비교해준다.

점화식은 다음과 같다.

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - L[i]] + J[i]);

 

---

 

메모리: 14196KB
시간: 176ms
언어: Java 11

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));
        StringTokenizer st;

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

        int[][] dp = new int[N + 1][100];
        for (int i = 1; i < N + 1; i++) {
            for (int j = 0; j < 100; j++) {
                if (L[i] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - L[i]] + J[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        System.out.println(dp[N][99]);
    }

}