[Baekjoon] 14501번: 퇴사 - Java

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

14501번: 퇴사

문제 설명

상담을 통한 최대 수익을 구하면 된다. 문제 이해는 크게 어렵지 않다.

풀이 방법

재귀를 활용한 완전탐색 방법을 사용할 수 있다. 이 방법은 시간 복잡도가 O(n^2)으로 문제 범위가 최대 15로 작아서 사용 가능하다. 범위가 커질 경우 DP를 활용해야 해결 가능할 것으로 보인다.

private static void solution(int day, int pay) {
    // 퇴사하는 날이 되면 최대 급여를 계산한다.
    if (day == N) {
        max = Math.max(max, pay);
        return;
    }

    // 퇴사하는 날을 넘기면 종료한다.
    if (day > N)
        return;

    // 상담하는 날은 상담 기간과 날짜를 더한 값과 급여를 더해서 넘겨준다.
    solution(T[day] + day, P[day] + pay);

    // 상담하지 못하는 날은 날짜만 늘리고 넘겨준다.
    solution(day + 1, pay);
}

전체 코드는 다음과 같다.

package baekjoon.brute_force;

import java.io.*;

public class BOJ14501 {

    static int N, max;
    static int[] T, P;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            N = Integer.parseInt(br.readLine());
            T = new int[N];
            P = new int[N];

            for (int i = 0; i < N; i++) {
                String[] split = br.readLine().split(" ");
                T[i] = Integer.parseInt(split[0]);
                P[i] = Integer.parseInt(split[1]);
            }

            solution(0, 0);

            System.out.println(max);
        }
    }

    private static void solution(int day, int pay) {
        // 퇴사하는 날이 되면 최대 급여를 계산한다.
        if (day == N) {
            max = Math.max(max, pay);
            return;
        }

        // 퇴사하는 날을 넘기면 종료한다.
        if (day > N)
            return;

        // 상담하는 날은 상담 기간과 날짜를 더한 값과 급여를 더해서 넘겨준다.
        solution(T[day] + day, P[day] + pay);

        // 상담하지 못하는 날은 날짜만 늘리고 넘겨준다.
        solution(day + 1, pay);
    }
}