[Algorithm] 백준온라인저지 14501번(BOJ 14501) 퇴사 Java풀이!! (DP)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 백준 온라인 저지에 있는 14501번 퇴사문제를 풀어보겠습니다.

 

1. 문제 설명

설명하기에 앞서 아래 링크를 통해서 문제를 읽고 와 주시길 바랍니다.

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

 

해당 문제의 접근법은 2가지가 있습니다.

1. 동적 계획법(Dynamic Programming)을 이용해서 푸는 방법
2. 완전 탐색을 통해서 푸는 방법

완전 탐색으로 푼 사람들의 코드를 보면 재귀 함수의 형태로 많이 구현하시는 것 같습니다.

둘 중 어느 방법을 통해서 구현해도 상관없지만 저는 동적 계획법(Dynamic Programming)을 이용해서 풀어보겠습니다.

 

우선 문제에서 주어진 조건을 다시 한번 살펴보겠습니다.

문제에서 N+1일에 퇴사를 하므로 N일까지 근무를 해야 하고 1~N일까지 근무를 할 때, 각 일자마다 정해진 상담업무가 있고 이를 할지 말지를 골라서 최대 비용이 되도록 해야 합니다.

또한, 1일 차에는 근무 가능한 일수가 N일이고, N일차에는 근무 가능한 일수가 1일이 됩니다.

일반적으로 이러한 문제에서 우리는 동적 계획법의 점화식을 해당 날짜의 근무를 선택할지 말지를 고려해서 작성하게 됩니다.

예를 들어 i가 일자를 의미할 때, dp[i]는 i일자까지 근무했을 때의 최대 비용이라고 할 수 있고 점화식은 다음과 같이 생각해 볼 수 있습니다.

• i일자의 상담을 진행하지 않는 경우 (상담을 진행하는 데 걸리는 시간 > 근무 가능 한일수)
  dp[i] = dp[i - 1]  (상담을 하지 않으므로, 그 전 일자의 최대 비용과 같음)
• i일자의 상담을 진행하는 경우 (상담을 진행하는 데 걸리는 시간 <= 근무 가능 한일수)
  dp[i] = max( dp[i-1], 해당 상담으로 버는 비용 + dp[i - 상담을 진행하는 데 걸리는 시간])

위의 점화식은 대표적인 DP문제인 배낭 문제에서처럼 특정 값을 선택할지 말지를 고려할 때 생각해볼 수 있는 점화식입니다.

그러나 퇴사문제는 위의 점화식으로 풀 수 없습니다.

왜냐하면 dp[1]일 때 1일 차에 근무 가능 한일수는 N일인데 점화식에서는 1로 체크되기 때문입니다.

 

그렇기 때문에 위의 점화식을 활용하기 위해서 우리는 발상을 좀 전환해서 주어진 정보를 뒤집어서 생각해봐야 합니다.

예를 들어 i를 근무 가능 일수라고 생각하면 dp[i]는 근무 가능 일수가 i만큼 남았을 때의 최대 비용이 됩니다.

그렇다면 dp[1]은 근무 가능 일수가 1일 때 최대 비용을 의미하고, 이때 상담업무는 N일차의 상담업무를 고려하면 됩니다.

dp[2]는 근무 가능 일수가 2일 남았을 때의 최대 비용을 의미하고, 이때 상담업무는 N-1일 차의 상담업무를 고려하면 됩니다.

이런 식으로 위의 점화식을 사용해서 값을 구하면 마지막에 N일차까지 근무했을 때의 최대 비용인 dp[N]을 구할 수 있습니다.

설명이 좀 길었습니다

사실 글로 설명하는 것보다 코드를 직접 보는 게 더 직관적으로 이해하실 수 있으므로 코드를 바로 작성해보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingnojam.algorithm;

import java.util.Scanner;

public class BOJ_14501 {

    // 백준온라인저지 14501번 퇴사문제 Java로 문제 풀이
    public static void main(String[] args) {

        // 입력정보 받을 객체
        Scanner sc = new Scanner(System.in);

        // 상담 가능한 일수
        int N = sc.nextInt();

        // 배열의 0인덱스를 안쓰기 위해 길이 1추가
        // 인덱스가 곧 근무일수가 됨
        int[][] info = new int[N+1][2];

        // 문제에서 주어지는 정보로 배열초기화
        // DP로 쉽게 풀기위해 정보를 거꾸로 받습니다.
        // 즉, 마지막날 상담정보가 배열의 제일 첫번째로
        // 이렇게 하는 이유는 배열의 인덱스가 근무 가능한 일수가 되야하므로
        // 예를들어 i가 1이면 1일짜리만 가능,
        // i가 5이면 5일이하의 상담만 가능
        // 이런식으로 하기 위해 뒤집어서 정보를 받아서 초기화합니다.
        for (int i = N; i > 0; i--) {
            int T = sc.nextInt();
            int P = sc.nextInt();
            info[i][0] = T;
            info[i][1] = P;
        }

        // DP를 위한 배열
        // DP배열 또한 인덱스를 날짜로 사용하기 위해 길이를 1증가
        int[] dp = new int[N + 1];

        // DP 배열을 채워갑니다.
        // dp[i]가 의미하는 바는 다음과 같습니다.
        // 근무 가능한 일수가 i일 때 최대 벌 수 있는 비용
        // dp[1]은 마지막날의 상담을 골라서 했을 떄 가지는 최대 비용값
        // dp[N]은 첫째날부터 마지막날까지 상담을 골라서 했을 때 가지는 최대 비용값
        // 왜그러냐면 마지막날인 경우를 보면 다음날 퇴사를 하기 때문에 근무가능한 일수가 1입니다.
        // 그러므로 i는 근무가능한 일수를 의미합니다.
        // 앞서 정보를 뒤집어서 저장한 이유도 이를 좀더 수월하게 하기 위해서입니다.
        for (int i = 1; i < dp.length; i++) {
            if (info[i][0] > i) {
                // 해당 일자에 주어진 상담업무를 할 수 없는 경우에는 제외하고
                // 그 전의 근무가능한 일자의 최대비용값을 가져옴
                dp[i] = dp[i - 1];
            } else {
                // 해당 일자에 주어진 상담업무를 할 수 있는 경우
                // 1. 상담업무를 하지 않았을 때의 경우와
                // 2. 상담해서 번 비용 + dp[근무가능일수 - 해당상담일자]
                // 1과 2를 비교해서 큰 값이 해당 dp의 값이 됩니다.
                // dp[근무가능일수 - 해당상담일자]의 값은 앞에서 미리 계산되어있습니다.
                dp[i] = Math.max(dp[i - 1], info[i][1] + dp[i - info[i][0]]);
            }
        }
		// 출력
        System.out.println(dp[N]);
    }

}

 

코드의 라인마다 주석을 통해 설명을 달아놓았으니 읽어보시길 바랍니다.

점화식은 앞서 설명한 점화식을 그대로 사용해서 구현하였습니다.

한 번에 이해가 되지 않으실 수도 있습니다.

코드에 값을 직접 대입해서 천천히 따라가면 수월하게 이해할 수 있을 거라 생각합니다.

감사합니다.

---