백준 15486: 퇴사 2 [골드 Ⅴ / JAVA]

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

15486번: 퇴사 2

---

 

• 알고리즘 : DP
• 풀이 날짜 : 과거, 2023.04.17, 2023.07.07. 리뷰

 

 

< 풀이 설명 >

무릇 DP 문제는, 어떤 상황이 정해져 있지 않을 때 주로 사용한다.

여러 상황 중에 가정하며 값을 할당하는 것이다.

 

이 문제에서 정해져 있지 않은 상황은 i 번째 날 근무 여부 이다.

그에 따라 다른 업무를 할 수 있는지에 영향을 주기 때문이다.

 

 

 

i 번째 날 근무를 해서 j - 1번째 날 일이 끝난다 할 때,

처음에는 i 번째 날 근무 여부에 따라 상황을 나눠서 금액을 저장하고자 했다.

dp[j][1] : 근무 할 수 있을 때
dp[j][0] : 근무 안(못) 했을 때

하지만 근무를 안 한다는 것은 못 한다는 것을 의미하고, 못 한 상황은 다른 날에 근무 했다는 것에 포함하므로,

근무를 한 경우만 생각해 주었다. 

 

 

i 번째 날 근무를 할 수 있을 때 최대 수입은,

i - 1 번째 날까지 받을 수 있는(i 번째 날 퇴사할 때) 최대 수입에, i 번째 날 임금을 더한 값이다.

 

그래서 다음과 같이 dp 배열을, dp [ j ] = j 번째 날 퇴사할 때 최대 수입( == i 번째 날 근무를 할 수 있을 때) 로 정의한다.

그럼 다음과 같이 식을 세울 수 있다.

dp[j]  = Max(dp[0 ~ i - 1]) + salary[i];
// j 번째 날 퇴사. j - 1 까지 근무
// j <= N

 

 

 

< 筆者의 辯 >

DP에서 어떻게 배열을 정의하느냐에 따라 효율성이 달라지는 것 같다.

 

 

처음에도 dp[ i ] 를, i 번째 날에 퇴사할 때 최대 수입 이라고 정의했다.

하지만 퇴사 날까지 할 수 있는 상담들을 다 저장해놓고, 각 날짜마다 각 상담들에 대해 iteration 돌려주었다.

dp 정의를 잘 활용하지 못해서, 최대 수입으로 가능한 날들이 더 다양해져서 구현하는 게 더 복잡하다.

 

 

다른 정의로는 dp[ i ] 를, i 번째 날부터 퇴사(N) 까지 일할 때 최대 수입이다.

그럼 i 번째 날에 일을 하느냐(dp[ j ] + pay[ i ]) , i + 1 번째 날부터 일을 하느냐(dp[ i + 1 ]) 로 나눌 수 있다.

 

 

 

i 번째 날 일을 하느냐, 안 하느냐로 기준을 나누는 것은 동일하지만

끝나는 날을 기준으로 할 때는, 앞에서부터 탐색하면 되지만 

시작하는 날을 기준으로 할 때는, 뒤에서부터 탐색하면 된다.

 

 

백준 14501번과 입력 크기만 다르고 문제는 동일하다.

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

14501번: 퇴사

 

 

 

< 코드 > 

1) i 번째 날에 퇴사할 때 최대 수입

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];

        int max = 0;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int dur = Integer.parseInt(st.nextToken());
            int pay = Integer.parseInt(st.nextToken());

            max = Math.max(max, dp[i]); /** continue 전, 놓치면 안 됨 **/
            if (i + dur > n) continue;

            dp[i + dur] = Math.max(max + pay, dp[i + dur]);
        }

        System.out.println(Math.max(max, dp[n]));
    }

}

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int dur = Integer.parseInt(st.nextToken());
            int pay = Integer.parseInt(st.nextToken());

            if (i + dur <= n) dp[i + dur] = Math.max(dp[i + dur], dp[i] + pay);

            dp[i + 1] = Math.max(dp[i], dp[i + 1]);
        }

        System.out.println(dp[n]);
    }

}

 

2) i 번째 날부터 퇴사(N) 까지 일할 때 최대 수입

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 2];
        int[] dur = new int[n + 1];
        int[] pay = new int[n + 1];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            dur[i] = Integer.parseInt(st.nextToken());
            pay[i] = Integer.parseInt(st.nextToken());
        }


        for (int i = n; i >= 0; i--) {
            if (i + dur[i] > n) dp[i] = dp[i + 1];
            else dp[i] = Math.max(dp[i + dur[i]] + pay[i], dp[i + 1]);
        }

        System.out.println(dp[0]);
    }

}

 

3) dp 정의를 잘 활용 못 했을 때

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

public class Main {

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

        int[] dp = new int[n + 2];  // 0 ~ n + 1
        int[] pay = new int[n + 1]; // 0 ~ n
        ArrayList<Integer>[] quit_day = new ArrayList[n + 2];
        for (int i = 0; i <= n + 1; i++) quit_day[i] = new ArrayList<>();

        for (int i = 1; i <= n; i++) { // 1일 부터
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int can_quit = i + Integer.parseInt(st.nextToken());
            pay[i] = Integer.parseInt(st.nextToken());

            if (can_quit <= n + 1) quit_day[can_quit].add(i);
        }


        // dp[i] : i 일에 퇴사일 때 최대 수입. i - 1 일까지 일할 수 있다
        int max = 0;
        for (int i = 2; i <= n + 1; i++) {
            int size = quit_day[i].size();

            if (size > 0) {
                for (int j = 0; j < size; j++) {
                    int tmp = quit_day[i].get(j);
                    dp[i] = Math.max(dp[i], dp[tmp] + pay[tmp]);
                }
            }

            // 꽉 채울 수 없을 때. i-1 일까지는 일하는 게 아닐 때
            /* 시간 초과
            for (int j = 2; j < i; j++)
               dp[i] = Math.max(dp[i], dp[j]);
             */
            dp[i] = Math.max(max, dp[i]);
            max = Math.max(max, dp[i]);
        }

        System.out.println(dp[n + 1]);
    }

}