[Algo] 백준 1535 안녕 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/1535

메모리 : 14556KB

시간 : 144ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] hp, happy;
    static int N, ans;
    static boolean[] check;

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        hp = new int[N];
        happy = new int[N];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            hp[i] = Integer.parseInt(st1.nextToken());
            happy[i] = Integer.parseInt(st2.nextToken());
        }
        ans = 0;
        check = new boolean[N];
        dfs(0, 100, 0);
        System.out.println(ans);
    }

    private static void dfs(int idx, int h, int p) {
        if (idx >= N)
            return;

        if (h <= 0)
            return;
        if (!check[idx]) {
            if (h - hp[idx] > 0) {
                check[idx] = true;
                ans = Math.max(p + happy[idx], ans);
                dfs(idx + 1, h - hp[idx], p + happy[idx]);
            }
            check[idx] = false;
            dfs(idx + 1, h, p);
        }
    }
}

풀이

인사를 하는 경우와 안하는 경우가 있기때문에 최대 2^20이고, 시간제한이 2초이기 때문에 완탐으로 해결!