자바(Java) 백준 14501 퇴사 풀이

문제

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

14501번: 퇴사

풀이

저는 dfs를 사용하여 풀었지만 해당 문제를 dp로 푸신 분들이 많네요. 이 문제의 의도 자체도 dp를 생각하고 만든 문제같긴합니다.
백트래킹을 조합해서 푸니까 시간 초과는 나지 않네요 130ms정도 걸렸습니다. dp로 풀고 싶은 분들은 다른 블로그를 참고해주세요.
제가 문제를 푼 방식은 다음과 같습니다.

• visited[i]에 i 날에 스케줄을 등록했는지 안했는지 체크해줍니다.
• dfs를 통해 1일부터 n 일까지 해당하는 날짜에 스케줄을 잡는 경우와 안 잡는 경우 2가지로 나눠서 탐색합니다.
• 해당하는 날짜에 스케줄을 잡으려면 isPos() 메서드를 통해 가능한지 여부를 확인합니다.
  • 해당 날짜의 스케줄이 n 일 이후에 끝나서 불가능한지 확인
  • 이전 날짜에 잡은 스케줄이 현재 날짜에도 일을 해야하는지 확인
• 2 조건을 통과한다면 다음날 스케줄도 같은 방식으로 탐색합니다.
• day가 n + 1이 되면 최대값을 갱신합니다.

코드

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

public class Main {

    private static int n;
    private static int[] terms;
    private static int[] profits;
    private static int max = 0;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        terms = new int[n + 1];
        profits = new int[n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            terms[i] = Integer.parseInt(st.nextToken());
            profits[i] = Integer.parseInt(st.nextToken());
        }
        dfs(1, 0);

        System.out.println(max);
    }

    public static void dfs(int day, int sum) {
        // day가 n + 1일이 되었다면 최대값 갱신
        if (day == n + 1) {
            max = Math.max(max, sum);
            return;
        }

        // 해당 날짜 스케줄을 하는 경우와 안하는 경우 2가지로 탐색합니다.
        dfs(day + 1, sum);
        // 해당 날짜 스케줄에 일하려면 일할 수 있는지 isPos() 메서드로 확인합니다.
        if (isPos(day)) {
            visited[day] = true;
            dfs(day + 1, sum + profits[day]);
            visited[day] = false;
        }
    }

    public static boolean isPos(int day) {
        // 만약에 해당 날짜 스케줄이 N일 보다 더 오래 걸리는지 확인합니다.
        if (day + terms[day] - 1 > n) {
            return false;
        }
        // 이전 날짜에 잡은 스케줄 중에 day 날에도 일하는 스케줄이 있는지 확인합니다.
        for (int i = 1; i < day; i++) {
            if (visited[i]) {
                if(i + terms[i] - 1 >= day) {
                    return false;
                }
            }
        }

        return true;
    }
}