백준 14501 퇴사 자바(java)

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

14501번: 퇴사

 

풀이 방법

DFS를 이용하여 상담 가능한 날짜 조합을 완전 탐색하여 해결하였다.

dfs 함수엔 현재 날짜와 이제까지의 누적된 이익을 넘겨준다.

현재 날짜를 i라고 할때 i일의 상담을 포함하는 경우와 포함하지 않는 경우 두 가지로 나누어 dfs 함수를 재귀 호출한다. 이때, i + T[i] 가 N+1 을 넘지 않는 경우에만 상담을 포함할 수 있도록 해야 한다.

현재 날짜가 N+1이 되면 이제까지 더한 이익을 비교하여 최대 이익을 갱신하고 탐색을 종료한다.

 

코드

import java.io.*;

public class Main {

    static int N;
    static int[][] arr;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][2];

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

        dfs(1, 0);
        System.out.println(answer);

    }

    public static void dfs(int day, int total) {
        if(day == N+1) {
            answer = Math.max(answer, total);
            return;
        }

        int t = arr[day][0]; // 기간
        int p = arr[day][1]; // 이익
        if(day+t <= N+1) { // N+1 일을 넘지 않는다면 포함 o
            dfs(day+t, total+p);
        }
        dfs(day+1, total); // 포함 x
    }
}