[백준 | java] 14501 퇴사

내 풀이

이 문제는 푸는 방법이 다음 두 가지가 있다.

• 브루트포스 백트래킹(DFS) 탐색
• DP

브루트포스 백트래킹(DFS) 탐색 방법

1. 날짜+상담을 완료하는데 걸리는 기간(T)이 N보다 작거나 같을 때 상담이 가능한 것이므로
   해당 날짜에 잡혀있는 상담의 받을 수 있는 금액(P)을 더해 탐색 진행
2. 날짜+상담을 완료하는데 걸리는 기간(T)이 N보다 클 때 상담이 불가능한 것이므로
   P의 최댓값을 구한 뒤 반환
3. DFS(i+1, p)를 DFS 끝에서 진행해
   상담이 시작되는 기준이 앞의 상담이 끝나는 경우가 아닌, 날짜를 기준으로 탐색 (1일부터 N일까지 모두 탐색 가능)

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

public class Main {
    static int[][] arr;
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        arr = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());  // T
            arr[i][1] = Integer.parseInt(st.nextToken());  // P
        }

        result = 0;
        DFS(0, 0);
        System.out.println(result);
    }
    static void DFS(int i, int p) {
        if (i >= arr.length) {
            result = Math.max(p, result);
            return;
        }

        if (i + arr[i][0] <= arr.length)  // 상담이 가능한 기간일 때 p 더해 백트래킹(dfs)
            DFS(i+arr[i][0], p+arr[i][1]);
        else  // 상담 기간이 퇴사일을 넘어갈 때 p는 더해지지 않고 종료조건으로 감
            DFS(i+arr[i][0], p);
        DFS(i+1, p);  // 1일부터 N일까지 각각 상담을 시작할 모든 경우 탐색
    }
}

DP

1. 테이블 정의
   • DP[i] = i+1번째 날 부터 상담 시 이익의 최댓값
   • DP[0] 찾기
2. 점화식 찾기
   • T[i] + i > N 일 떄
     • i번쨰 날짜엔 상담할 수 없음
       👉 DP[i] = DP[i+1]
   • T[i] + i <= N 일 떄
     • i번째 날짜에 상담할 수 있음
     • 다음 1과 2 중 더 큰 값이 DP[i]
       1. i번쨰 날짜에 상담을 하지 않을 때
          👉 DP[i] = D[i+1]
       2. i번째 날짜에 상담을 할 때
          👉 DP[i] = P[i] = DP[i+T[i]]
3. 초기값 찾기
   • DP[N-1]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] T = new int[N];
        int[] P = new int[N];
        int[] DP = new int[N+1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = N-1; i >= 0; i--) {
            if (i+T[i] > N)  // i에 상담할 수 없을 때
                DP[i] = DP[i+1];
            else  // i에 상담할 수 있을 때
                DP[i] = Math.max(DP[i+1], P[i]+DP[i+T[i]]);  // max(i에 상담하지 않았을 때, i에 상담했을 때)
        }
        System.out.println(DP[0]);
    }
}