[백준](Java) 14501 - 퇴사

문제 링크

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

문제 풀이

완전 탐색을 돌려 가장 큰 값을 찾을 수 있도록 접근했다.
일의 날짜와, 돈을 담는 Counsel 이라는 Class를 담는 List를 만들었다.

탐색의 시작은 bf(0) 부터 시작했고 재귀를 반복하며 사용할 arraylist를 parameter로 같이 사용하였다.
기본적인 dfs처럼 한번 방문했던 index는 들리지 않도록 했고
조건에 맞으면 arraylist에 담아주고
담은 값의 시간만큼 인덱스를 증가시켜 다음 재귀로 넘어갔다.

        for (int i = idx; i < n; i++) {
            if (chk[i]) {
                continue;
            }
            res.add(new Counsel(counselList.get(i).time, counselList.get(i).money));
            chk[i] = true;
            bf(i + counselList.get(i).time, res);
            res.remove(res.size() - 1);
            chk[i] = false;
        }

index가 퇴사일(n)이 되었을 경우 (1부터 시작하면 n+1)보다 크거나 같아지면
더 이상 일을 할수가 없다.
logic상 맨 마지막 값을 입력받았을때 퇴사일을 넘어가는 것이므로 res의 마지막 값은 빼고 보수들을 더했고, 마지막 퇴사일전날에 걸치는 경우에는 일을 할 수 있으므로 idx==n인 경우에는 마지막 값을 더해주었다.

        if (idx >= n) {
            int sum = 0;
            for (int i = 0; i < res.size() - 1; i++) {
                sum += res.get(i).money;
            }
            if (idx == n) {
                sum += res.get(res.size() - 1).money;
            }
            answer = Math.max(answer, sum);
            return;
        }

코드

import java.util.*;


public class Main {

    static int n;
    static List<Counsel> counselList = new ArrayList<>();
    static boolean[] chk;
    static int answer = 0;

    public static class Counsel {
        int time;
        int money;

        public Counsel(int time, int money) {
            this.time = time;
            this.money = money;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            counselList.add(new Counsel(sc.nextInt(), sc.nextInt()));
        }
        chk = new boolean[counselList.size()];

        bf(0, new ArrayList());
        System.out.println(answer);
    }

    public static void bf(int idx, ArrayList<Counsel> res) {

        if (idx >= n) {
            int sum = 0;
            for (int i = 0; i < res.size() - 1; i++) {
                sum += res.get(i).money;
            }
            if (idx == n) {
                sum += res.get(res.size() - 1).money;
            }
            answer = Math.max(answer, sum);
            return;
        }

        for (int i = idx; i < n; i++) {
            if (chk[i]) {
                continue;
            }
            res.add(new Counsel(counselList.get(i).time, counselList.get(i).money));
            chk[i] = true;
            bf(i + counselList.get(i).time, res);
            res.remove(res.size() - 1);
            chk[i] = false;
        }
    }
}