백준 1535번 : 안녕(Java)

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

1535번: 안녕

---

[풀이]

 

• 재귀(dfs)를 이용해서 문제를 풀었습니다.
• 기쁨에 해당하는 배열은 값을 더하고, 체력에 해당하는 배열은 값을 빼는 방식으로 진행했습니다.
• 인덱스에 해당하는 변수를 이용해서 N 변수와 같게 된다면 재귀 횟수를 종료합니다.

---

[코드]

 

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

public class Main {
    static int N, answer;
    static int[] L, J;

    public static int dfs(int idx, int joy, int health) {
        if (N == idx && health > 0) {
            answer = Math.max(answer, joy);
            return answer;
        }
        if (health > 0) {
            dfs(idx + 1, joy + J[idx], health - L[idx]);
            dfs(idx + 1, joy, health);
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        L = new int[N];
        J = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            L[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            J[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0, 100);

        System.out.println(answer);
    }
}