[boj] 14501번: 퇴사

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

14501번: 퇴사

 

 

 

1. 문제 설명 

백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서 남은 N일 동안 최대한 많은 상담을 하려고 한다. 최대 수익을 구하라.

 

 

 

2. 접근 방식 

dp로 접근했다. dp = new int[n+1]로 초기화해서 N+1일째 되는 날까지 값을 갱신해준다. 각 0일부터 N일까지 반복하면서 '현재 요일까지 벌어들인 수익 + 현재 상담을 시작해서 끝나는 날에 받는 수익' 과 '끝나는 날에 벌어들인 수익'을 비교한다.

 

for(int i = 0; i < n; i++) 

    for(int j = i + arr[i].time; j < n+1; j++)

        if(dp[j] < dp[i] + arr[i].profit)

            dp[j] = dp[i] + arr[i].profit

 

 

예를 들어보자. dp = [0, 0, 0, 0, 0, 0, 0, 0] 일 때, 1일에 상담을 시작해서 3일 뒤에 끝나면 4일이 된다. 1일에 상담을 시작해 4일에 상담을 끝냈을 때(dp[0] + arr[0].profit) 가지고 있는 수익은 0 + 10 = 10원(편의상 원으로 가정)이다. 그리고 4일에 갖고 있던 수익(dp[3]) 과 비교한다. 0 < 10 이므로 dp[3]의 배열은 10으로 갱신된다. 그 뒤의 요일들도 모두 0이기 때문에 N+1일까지 10으로 갱신될 것이다. 

 

현재 1일에 상담을 시작했을 경우의 수익을 갱신한 상태다.             

dp = [0,   0,   0,   10,  10,    10,    10,      10]                                            

        1일 2일 3일 4일  5일  6일  7일(N일)  N+1일

 

2일에 상담을 시작한 경우, 2일에 상담을 시작하면 5일 뒤에 수익을 얻을 수 있다. 

dp[1] + dp[1].profit > dp[6] 을 비교해보면 20 > 10 이 된다. 이런 식으로 계속 갱신해준다.

.

.

.

5일차의 상담을 하는 경우를 살펴본다. 현재 4일차까지 갱신된 dp배열은 [0, 0, 0, 10, 30, 30, 30, 30] 이다.

현재(5일차)까지 벌어들인 최대 수익은 30원이다. 5일차에 상담을 시작한다면 2일이 걸리고 수익은 15원을 얻을 수 있다. 5일차에 상담을 시작해서 7일 차에 벌 수 있는 수익(15) + 5일차까지 벌어들인 수익(30) > 7일차까지 벌어들인 수익(30) 은 45로 갱신된다. 최종적인 dp 배열은 [0, 0, 0, 10, 30, 30, 45, 45]가 된다. 마지막 N+1일째가 되었을 때까지 벌어들인 수익을 출력해주자 !

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

package samsungCodingTest.Week04;

import java.io.*;
import java.util.StringTokenizer;

public class BOJ14501 {
    static class Pair<T, P> { // pair 클래스 구현 Time, Profit을 받기 위해
        T time;
        P profit;

        public Pair(T timeValue, P profitValue) {
            time = timeValue;
            profit = profitValue;
        }
    }
    static Pair<Integer, Integer>[] arr; 
    static int n ;
    static int[] dp;

    static FastReader scan = new FastReader();

    public static void main(String[] args) throws IOException {


        n = scan.nextInt(); 
        dp = new int[n+1]; // N+1일만큼의 dp 배열
        arr = new Pair[n+1]; // N+1개의 상담완료 기간, 받을 수 있는 금액을 저장하기 위한 배열
        for (int i = 0; i < n; i++) {
            int t = scan.nextInt(), p = scan.nextInt();
            arr[i] = new Pair<>(t, p); // Use dynamic arr of pairs.
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + arr[i].time; j < n+1; j++) {
                if (dp[j] < dp[i] + arr[i].profit)
                    dp[j] = dp[i] + arr[i].profit;
            }
        }
        System.out.println(dp[dp.length-1]);
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

 

 

4. 분석 및 시간복잡도 

시간복잡도 : O(N^2) 

 

dp 테이블을 정의하는 연습을 많이 해야겠다.. 아직 dp는 쉽지 않다..