[백준] 14501번 : 퇴사 (JAVA)

인간몽쉘김통통·2023년 11월 14일

백준

목록 보기

14/92

문제

이해

일정표를 보고 가능한 경우 중에서 최대 수익을 구하는 프로그램을 작성하면 된다.

T는 상담소요일수, P는 금액이다. 상담은 N번째날 당일부터 시작하여 N+Tn-1 날까지 진행된다. 예시의 1일차에 상담을 시작하면 소요일수는 3일이므로 1, 2, 3일 상담을 진행하고 4일날부터 새로운 상담을 시작할 수 있다.

소요일수가 하루인 경우 당일날 시작하여 끝낼 수 있다.

접근

가능한 경우를 탐색하는 문제이기 때문에 최초에 브루트포스를 생각하였다. 그 중에서 dfs를 이용하여 각 가능한 경우를 탐색하고 재귀의 끝에서 최대값을 갱신하도록 설계하였다.

소요일수가 1, 금액이 0인 0번째날에 무조건 상담한다고 가정하고 각 상담일을 결정하는 경우를 생각해보았다.

0번째날부터 dfs를 수행하여 선택할 수 있는 경우를 모두 거치게 하여 최대값을 추출하였다.

하지만 dfs를 사용할 경우 최초에 0일이후로 선택될 1일~N일 (depth:1) 의 경우 dfs가 수행되면서 불필요한 반복이 발생한다.

문제는 N이 최대 15밖에 되지 않기 때문에 큰 문제가 발생하지 않지만 N이 커지면 시간적으로 효율이 좋지 않다.

다른 방법으로는 다이나믹 프로그래밍을 생각해보았다. 각 날짜를 선택했을 때 최대값을 배열로 나타내고 dp로 배열의 값을 저장하는 방식으로 설계했다.

max[i]은 i일부터 선택될때의 최대값이 된다.

점화식으로 나타내면

max[i] = pay[i] + max[i + 소요일수] (i번째날 상담하는 경우)
= 최대값(max[i], max[i+1], ... , max[n])

점화식의 아래 경우는 i번째날 상담하는 것이 오히려 손해인 경우이다.

아래는 각각 DFS, DP를 활용한 코드이다.

코드

DFS

package java_baekjoon;

import java.util.*;

public class prob14501 {
    static int N;
    static int max = 0;
    static int[] need_day;
    static int[] pay;

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

        N = sc.nextInt();

        need_day = new int[N+1];
        need_day[0] = 1;
        pay = new int[N+1];

        for (int i = 1; i <= N; i++) {
            need_day[i] = sc.nextInt();
            pay[i] = sc.nextInt();
        }

        dfs(0, 0);

        System.out.println(max);
    }

    static void dfs(int day, int sum_of_pay) {
        if (day + need_day[day] - 1 > N) {
            if (max < sum_of_pay) {
                max = sum_of_pay;
            }
            return;
        }

        sum_of_pay += pay[day];

        if(day + need_day[day] - 1 == N){
            if(max < sum_of_pay){
                max = sum_of_pay;
            }
            return;
        }

        for (int i = day + need_day[day]; i <= N; i++) {
            dfs(i, sum_of_pay);
        }
    }
}

DP

package java_baekjoon;

import java.util.*;

public class prob14501_2 {
    static int N;
    static int[] need_day;
    static int[] pay;
    static int[] max;
    static int current = 0;

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

        N = sc.nextInt();

        need_day = new int[N + 1];
        need_day[0] = 1;
        pay = new int[N + 1];
        max = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            need_day[i] = sc.nextInt();
            pay[i] = sc.nextInt();
        }

        if (need_day[N] == 1) {
            max[N] = pay[N];
        } else {
            max[N] = 0;
        }
        current = max[N];

        for (int i = N - 1; i >= 0; i--) {
            if (i + need_day[i] - 1 < N) {
                max[i] = pay[i] + max[i + need_day[i]];
            } else if (i + need_day[i] - 1 == N) {
                max[i] = pay[i];
            } else {
                max[i] = 0;
            }
            
            if(max[i] < current){
                max[i] = current;
            }else{
                current = max[i];
            }
        }

        System.out.println(current);
    }
}