퇴사

📍 문제 설명

 

💡 접근

책에서 DP를 이용해서 푸는 방법을 학습했으나 브루트포스 카테고리로 분류되어 있어서 브루트포스로 풀었다.

최대점수 구하기 문제와 비슷하게 상담을 진행한다/진행하지 않는다로 분류해야 한다.

진행하지 않는 경우도 고려해야 하는 이유는 해당 상담을 진행하지 않았을 때 얻게 되는 최종 금액이 더 클 수도 있기 때문이다.

 

👩‍💻 코드

1.브루트포스

import java.util.*;

public class Main {
    static int n, m, answer, sum;
    static int[][] board,clone;
    static boolean[] arr;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static StringBuilder sb = new StringBuilder();
    static ArrayList<Consulting> list = new ArrayList<>();

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

        n = kb.nextInt();
        kb.nextLine();
        for(int i = 0; i < n; i++) {
            String[] s = kb.nextLine().split(" ");
            list.add(new Consulting(Integer.parseInt(s[0]), Integer.parseInt(s[1])));
        }

        //누적 시간, 누적 금액
        T.solution(0, 0);
        System.out.println(answer);

    }

    private void solution(int day, int sum) {
        if(day == n) {
            answer = Math.max(answer, sum);
            return;
        }
        //해당 날짜에 상담이 가능하면 상담을 진행 한다.
        if(day + list.get(day).time <= n) {
            solution(day+list.get(day).time, sum+list.get(day).price);
        }
        //해당 날짜에 상담을 하지 않고 다음 날로 가본다.(예제 4와 같은 경우때문에)
        solution(day+1, sum);
    }


    private static class Consulting {
        private int time;
        private int price;

        public Consulting(int time, int price) {
            this.time = time;
            this.price = price;
        }

        @Override
        public String toString() {
            return "Consulting{" +
                    "time=" + time +
                    ", price=" + price +
                    '}';
        }
    }
}

 

2.DP

import java.util.*;

public class Main {
    static int n, m, answer, sum;
    static int[][] board,clone;
    static boolean[] arr;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static StringBuilder sb = new StringBuilder();
    static int maxValue;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int[] t = new int[n];
        int[] p = new int[n];
        for(int i = 0; i < n; i++) {
            t[i] = kb.nextInt();
            p[i] = kb.nextInt();
        }

        //dp[i]는 i일의 상담에서 얻을 수 있는 최대 금액이다. n-1일부터 0일
        int[] dp = new int[n+1];
        for(int i = n-1; i >= 0; i--){
            //상담을 완료하는데 드는 총 시간
            int time = t[i] + i;
            //해당 시간이 n보다 작거나 같아야 상담이 가능하다.
            if (time <= n) {
                //현재 까지의 최고 이익 계산
                dp[i] = Math.max(p[i] + dp[time], maxValue);
                maxValue = dp[i];

            }
            //현재 날짜에 상담이 불가능하면
            else dp[i] = maxValue;
            System.out.println("i : " + i);
            System.out.println("time : " + time);
            System.out.println("maxValue : " + maxValue);
            System.out.println();
        }
        System.out.println(Arrays.toString(dp));
    }
}