BOJ14501 퇴사

https://www.acmicpc.net/problem/14501 (opens new window)

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

dfs 활용

private static void dfs(int day, int pay) {

    if (day == n + 1) { // (1)
        result = Math.max(result, pay);
    }

    if (day > n) { // (2)
        return;
    }

    dfs(day + t[day], pay + p[day]); // (3)
    dfs(day + 1, pay); // (4)
}

(1) day가 n + 1이 되는 날 퇴사를 진행하고 pay를 지급받는다. (2) result에 pay의 가장 큰 값을 저장한다. day > n 경우에는 더 이상 일을 진행할 수 없기 때문에 반환한다. (3) 일을 진행한다고 가정하고 dfs를 진행한다. (4) 일을 진행하지 않는다고 가정하고 dfs를 진행한다.

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ14501 {

    private static int n, result;
    private static int[] t, p;

    private static void dfs(int day, int pay) {

        if (day == n + 1) {
            result = Math.max(result, pay);
        }

        if (day > n) {
            return;
        }

        dfs(day + t[day], pay + p[day]);
        dfs(day + 1, pay);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        t = new int[n + 1];
        p = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            t[i] = scanner.nextInt();
            p[i] = scanner.nextInt();
        }

        dfs(1, 0);

        System.out.println(result);
    }
}

#BOJ #다이나믹 프로그래밍 #브루트포스 알고리즘 #dfs