알고리즘 풀이 - 백준 14501(퇴사, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

퇴사하고자 하는 상담사. N+1일 후 퇴사 시, N일 간 최대한 많은 상담을 하고자 할 때, 상담으로 얻는 수익의 최대값을 구하는 문제

 

 

2. 풀이

 

이 문제는 완전 탐색(재귀) 와 DP를 이용한 해결이 모두 가능한 문제이다.

 

① 완전 탐색으로 해결하기

각 상담 일자에 상담을 시도하여 가능한 경우를 모두 테스트 후 그 결과 중 가장 수익이 높은 경우를 비교할 수 있다.

즉, 1일차에 상담을 시작 후 상담이 끝난 일자 부터 그 이후에 상담이 가능한 모든 일자에 테스트를 하고 그 결과 값을 저장한다.

같은 방법을 2일차부터 N일차에 시작하여 동일하게 결과를 얻고 그 결과를 비교하여 가장 높은 수익을 얻는 경우를 찾는다.

 

② DP로 해결하기

DP를 통해 해결 가능한 경우 또한 살펴보자. DP 관련 포스팅은 여기를 참조

n번째 일자에 상담이 끝났다면 n-1번째 일자 까지 중 상담을 최대로 진행하여 n번째 일자에 상담이 끝나는 경우의 이익을 구하는 것과 같다.

이 과정이 1~N+1일차의 일자에 상담이 끝나는 경우에 모두 동일하게 적용 된다. 따라서 작은 문제가 동일하게 반복되며 그 결과를 큰 문제를 해결 시에 그대로 활용 가능하다!

DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족하기에 DP로 해결이 가능하다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① 완전 탐색으로 해결하기

import java.io.*;

public class Main{
    static int n;
    static int[] T;
    static int[] P;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        T = new int[n+1];
        P = new int[n+1];

        for(int i=1; i <= n; i++){
            String[] line = br.readLine().split(" ");
            T[i] = Integer.parseInt(line[0]);
            P[i] = Integer.parseInt(line[1]);
        }

        int ans = 0;
        
        // 상담 시작일자를 반드시 1일부터가 아닌 이후부터 시작할 수도 있음을 판단 해야한다.
        for(int i=1; i <= n; i++){
            ans = Math.max(ans, solve(i+T[i], P[i]));
        }
        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    // 상담 진행 후 일자가 함수의 상태값이 된다.
    // 가장 큰 경우를 구해야 하므로 수익 값을 반환한다.
    private static int solve(int day, int profit){
        if(day > n+1) return 0;

        int temp = profit;
        
        // 현재 상담 후 일자부터 진행이 가능함! temp에 미리 저장해두고 기존 이득 + 상담 이득을 비교한다.
        for(int i=day; i <= n; i++){
            temp = Math.max(temp, solve(i+T[i], profit+P[i]));
        }
        return temp;
    }
}

 

② DP로 해결하기

import java.io.*;

public class Main{
    static int n;
    static int[] T;
    static int[] P;
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        
        // n+2로 하는 이유는 1~n까지의 index를 사용하는데, n일자에 1일짜리 일도 가능하기 때문
        // 따라서 n+2로 저장
        T = new int[n+2];
        P = new int[n+2];
        dp = new int[n+2];

        for(int i=1; i <= n; i++){
            String[] line = br.readLine().split(" ");
            T[i] = Integer.parseInt(line[0]);
            P[i] = Integer.parseInt(line[1]);
        }

        int max = 0;
        
        for(int i=1; i <= n+1; i++){
            // 현재 최대값은 i일자 때의 최대 상담 이익 값과 비교한다.
            max = Math.max(max, dp[i]);
        
            // 현재 일자에서 상담 후 끝나는 일자 확인
            int end = T[i] + i;
            
            // 마지막 일자에 1일 짜리 상담은 가능하니, 상담 후 일자는 n+1일까지 가능하다.
            // 이전 날짜들에 의해 상담 후 끝나서 저장된 현재 이익 값과
            // 현재까지의 최대값에 중간 건너뛰거나(혹은 안뛰고) i날짜에 상담 후 얻은 이익을 비교
            if(end <= n+1) {
                dp[end] = Math.max(dp[end], max+P[i]);
            }
        }
        bw.write(String.valueOf(max));
        bw.flush();
        br.close();
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.