[백준] 14501번 : 퇴사 - 자바[Java]

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

14501번: 퇴사

풀이

상담을 할 수 있는 가능한 모든 경우를 구한 다음 그 중에서 최대 수익을 구해야 한다.

 

예시를 들어 설명하겠다.

 

먼저 1일에 상담을 한다고 가정했을 경우(현재 수익 10), 2, 3일은 할 수 없으므로 4일로 넘어간다. 4일에 상담을 한다고 가정하면(현재 수익 30), 5일로 넘어가고 또 이때 5일에 상담을 한다고 가정하면(현재 수익 45), 7일로 넘어간다. 7일에는 상담을 할 수 없으므로 총 수익은 45가 된다.

총 수익을 구한 다음 가장 최근 분기였던 5일째로 돌아간다. 5일에 상담을 하지 않는다고 가정하면(현재 수익 30), 6일로 넘어간다. 6일에는 상담을 할 수 없으므로 총 수익은 30가 된다.

총 수익을 구했으면 그 이전 분기였던 4일째로 돌아간다. 4일에 상담을 하지 않는다고 가정하면(현재 수익 10), 5일로 넘어간다. 5일에 상담을 한다고 가정하면(현재 수익 25), 7일로 넘어간다. 7일에는 상담을 할 수 없으므로 총 수익은 25가 된다.

 

위 과정을 간략화 하면 다음과 같다.

1일 상담 o -> 4일 상담 o -> 5일 상담 o : 총 수익 45
                                        -> 5일 상담 x : 총 수익 30
                  -> 4일 상담 x -> 5일 상담 o : 총 수익 25
...
1일 상담 x -> 2일 상담 o -> ...
...

 

이러한 과정을 반복하여 상담을 할 수 있는 모든 경우를 구하고, 그 중 최대 수익을 구하면 된다.

모든 경우를 탐색할 때 DFS를 사용한다.

로직

1. 내부 클래스 Work를 선언한다. Work는 상담의 정보를 저장하는 클래스이며 멤버 변수로 t와 p를 가진다. t는 상담을 완료하는데 걸리는 기간, p는 상담을 했을 때 받을 수 있는 금액이다.

2. 정답을 저장할 answer를 static 변수로 선언하고 0으로 초기화한다.

3. n을 입력받는다.

4. 상담의 정보를 저장하는 ArrayList<Work> list를 선언한다.

5. 각각의 상담의 t와 p를 입력받고 상담을 list에 추가한다.

6. findMaxProfit() 함수를 호출한다.

7. answer를 출력한다.

 

void findMaxProfit(int n, ArrayList<Work> list, int day, int sum) : DFS를 수행하여 상담을 할 수 있는 모든 경우를 구하여 최대 수익을 answer에 저장한다.

    static void findMaxProfit(int n, ArrayList<Work> list, int day, int sum) {

        //상담을 더 이상 진행할 수 없는 경우
        if (day >= n) {
            answer = Math.max(answer, sum);
            return;
        }

        Work cur = list.get(day); //현재 날짜의 상담

        //현재 날짜의 상담을 할 수 있는 경우
        if (day + cur.t <= n) {
            findMaxProfit(n, list, day + cur.t, sum + cur.p);
        }

        //현재 날짜의 상담을 하지 않는 경우
        findMaxProfit(n, list, day + 1, sum);

    }

n : 상담 일 수

list : 상담의 정보를 저장한 ArrayList

day : 현재 날짜 (0부터 시작)

sum : 현재 총 수익

• day가 n 이상이면 더 이상 상담을 할 수 없으므로 answer 값을 업데이트하고 리턴한다.
• 현재 날짜의 상담(cur)을 구한다.
• 현재 날짜의 상담을 할 수 있으면(day + cur.t <= n),  findMaxProfit(n, list, day + cur.t, sum + cur.p)을 호출한다.
• 현재 날짜의 상담을 하지 않는 경우, findMaxProfit(n, list, day + 1, sum)을 호출한다.

 

코드 - DFS

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

public class Main {

    static class Work{
        int t; //걸리는 기간
        int p; //받을 수 있는 금액

        public Work(int t, int p) {
            this.t = t;
            this.p = p;
        }
    }

    static int answer = 0;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        ArrayList<Work> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            list.add(new Work(t, p));
        }

        findMaxProfit(n, list, 0, 0);

        System.out.println(answer);
    }

    static void findMaxProfit(int n, ArrayList<Work> list, int day, int sum) {

        //상담을 더 이상 진행할 수 없는 경우
        if (day >= n) {
            answer = Math.max(answer, sum);
            return;
        }

        Work cur = list.get(day); //현재 날짜의 상담

        //현재 날짜의 상담을 할 수 있는 경우
        if (day + cur.t <= n) {
            findMaxProfit(n, list, day + cur.t, sum + cur.p);
        }

        //현재 날짜의 상담을 하지 않는 경우
        findMaxProfit(n, list, day + 1, sum);

    }

}

 

---

다른 풀이 2 - DP (동적 계획법)

이 문제의 풀이를 구글링한 결과 대부분 DP를 사용해서 풀었다.

즉, 1차원 배열 dp를 선언한 후, dp[i]에 i번째 날짜까지 상담했을 때 얻을 수 있는 최대 이익을 저장하여 N일까지 상담을 할 때 얻을 수 있는 최대 이익을 구한다.

주의할 점

• dp[i]에서 i는 0부터 시작한다. (문제에서는 1일부터 나와있지만 실제로 풀 때는 0일부터 시작한다.)
• 1일 차에 1일짜리 일을 한다면 2일 차에 돈을 받는다고 가정 -> 최종적으로 구해야하는 최대 이익은 dp[n]에 저장된다.

 

로직

1. n을 입력받는다.

2. 1차원 배열 t와 p를 선언하고 크기는 n만큼 할당한다. 각각 i번째 날짜의 상담의 상담을 완료하는데 걸리는 기간Ti와 상담을 했을 때 받을 수 있는 금액 Pi를 저장한다.

3. 각각의 상담의 t와 p를 입력받고 각각 t, p 배열에 저장한다.

4. 1차원 배열 dp를 선언하고 크기는 n+1만큼 할당한다. dp[i]는 i일에 얻을 수 있는 최대 이익을 저장한다. i는 0부터 시작하며 dp 값은 0으로 모두 초기화되어있다.

5. 각 상담에 대해 다음을 수행한다.

• 현재 날짜(i)의 상담을 할 수 있는 경우, 현재 날짜의 상담을 완료하는 날짜(i+t[i])의 dp 값을 업데이트한다.
• 현재 날짜(i)의 상담을 하지 않는 경우를 고려하여, 현재 날짜의 다음 날(i+1)의 dp 값을 업데이트한다.

6. dp[n]을 출력한다.

 

코드

import java.io.*;
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());
        StringTokenizer st;

        int[] t = new int[n];
        int[] p = new int[n];

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

        int[] dp = new int[n+1]; // N일에 얻을 수 있는 최대 이익

        for (int i = 0; i < n; i++) {
            //현재 날짜의 상담을 할 수 있는 경우
            if (i + t[i] <= n) {
                dp[i+t[i]] = Math.max(dp[i+t[i]], dp[i] + p[i]);
            }

            //현재 날짜에 상담을 하지 않는 경우를 고려하여, (현재 날짜의 + 1)일에는 현재 날짜까지 일한 최대 이익을 넣어주어야 한다.
            dp[i+1] = Math.max(dp[i+1], dp[i]);
        }

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

}

참고: https://hidelookit.tistory.com/m/118

 

---

위가 2번째 풀이(DP), 아래가 1번째 풀이(DFS)

두 풀이 방법 모두 실행 시간은 비슷하며 2번째 풀이가 근소한 차이로 메모리를 더 적게 사용하는 것을 확인할 수 있다.

코드 길이는 2번째 풀이가 더 적게 사용하는 것을 볼 수 있다.