[DP]백준 14501 퇴사, 15486 퇴사 2

< 반복문 버전 >

package DP;

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

public class boj_14501_퇴사 {
    // 1. 뒤에서 부터 For문을 돌기
    // 2. 해당 배열 순서 + 경과 기간 >= N 이면 넘기기
    // 3. 합의 최댓값 으로 갱신 해두기
    static class Consult {
        int time;
        int profit;

        Consult(int time, int profit) {
            this.time = time;
            this.profit = profit;
        }

    }
    public static void main(String[] args) throws IOException {
//        Scanner br = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int max = 0;
        int curProfit = 0;
        int N = Integer.parseInt(br.readLine());
        Consult[] consults = new Consult[N];
        int dp[] = new int[N+1];

        for (int i = 0; i < N; i++) {
            String temp[] = br.readLine().split(" ");
            consults[i] = new Consult(Integer.parseInt(temp[0]), Integer.parseInt(temp[1]));
        }

        for (int i = N - 1; i >= 0; i--) {
            if(consults[i].time + i <= N){
                curProfit = consults[i].profit + dp[i + consults[i].time];
                max = Math.max(curProfit, max);
                dp[i] = max ;
            } else {
                dp[i] = max;
            }
        }

        System.out.print(max);
    }
}

< 재귀함수 버전 >

package DP;

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

// DP
// 1. 템플릿 적용
// 2. 백트래킹
// 3. 메모이제이션 적용

public class boj_14501_퇴사_재귀함수 {
    // 1. 뒤에서 부터 For문을 돌기
    // 2. 해당 배열 순서 + 경과 기간 >= N 이면 넘기기
    // 3. 합의 최댓값 으로 갱신 해두기
    static class Consult {
        int time;
        int profit;

        Consult(int time, int profit) {
            this.time = time;
            this.profit = profit;
        }

    }
    private static int dp[], N, max;
    private static Consult[] consults;
    public static void main(String[] args) throws IOException {
//        Scanner br = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        max = -10000000;
        dp= new int[N];

        int curProfit = 0;
        consults = new Consult[N];

        for (int i = 0; i < N; i++) {
            String temp[] = br.readLine().split(" ");
            consults[i] = new Consult(Integer.parseInt(temp[0]), Integer.parseInt(temp[1]));
            dp[i] = -1;
        }

        System.out.print(recur(0));
    }

    private static int recur(int cur) {
        if(cur > N) return Integer.MIN_VALUE;

        if(cur == N) return 0;

        if(dp[cur] != -1) return dp[cur];

        dp[cur] = Math.max(recur(cur + consults[cur].time) + consults[cur].profit, recur(cur + 1));

        return dp[cur];
    }
}

 

14501 문제는 부분집합으로도 풀어도 되지만 어차피 두 문제는 같은 문제이므로 DP로 풀었다.

 

단순 알고리즘 풀이에는 Class정의 따로 안하고 풀었었는데 디버깅 시간을 줄이고, 가독성을 향상 시키기 위해서 Consult 클래스를 별도로 정의해서 사용코자 했다. getter, setter는 알고리즘에 투머치인 것 같아서 클래스 속성(attributes)에 접근하였다.