백준-14501번/퇴사 (java)

 

 

문제 이해

 

T[i] ==> 상담하는데 걸린 시간

P[i] ==> 상담으로 받는 금액

 

정해진 시간안에 받을 수 있는 최대 금액을 구하는 문제이다.

 

DFS를 이용하면 DP를 이용하는 것 보다 쉽게 구할 수 있다.

 

DFS 탈출 조건

==> 현재 날짜에서 상담에 걸리는 시간을 더했을때 N보다 크거나 같을 경우

 

문제 풀이

<dfs 메서드>

static void dfs(int idx, int pay){
    if(idx>=N){
        result = Math.max(pay,result);
        return;
    }
    if(idx+T[idx]<=N){
        dfs(idx+T[idx],pay+P[idx]);
    }else{
        dfs(idx+T[idx],pay);
    }

    dfs(idx+1,pay);
}

 

idx+T[idx]가 N 보다 작을 경우 즉, 상담을 할 수 있는 경우 재귀 호출을 이용해서 상담을 완료한 다음 날짜와 누적 금액을 넘겨준다.

 

상담이 불가능한 경우 다음 날짜와 가격만 넘겨줘서 가격이 누적되지 않게 해준다.

 

★ 이러한 방식으로 한다면 모든 경우의 수를 구할 수 없다.

상담에 걸리는 시간때문에 건너뛰는 날짜가 있으므로 그러한 경우까지 다 구해줘야한다 따라서 아래 코드를 DFS 메서드에 추가해준다.

dfs(idx+1,pay);

 

 

 

<전체 코드>

import java.util.Scanner;

public class Problem14501_2 {
    static int N;
    static int[] T,selected;
    static int[] P;
    static int result;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N=scanner.nextInt();
        T=new int[N];
        P=new int[N];
        result=0;
        for(int i=0; i<N; i++){
            T[i]=scanner.nextInt();
            P[i]=scanner.nextInt();
        }
        dfs(0,0);
        System.out.println(result);
    }

    static void dfs(int idx, int pay){
        if(idx>=N){
            result = Math.max(pay,result);
            return;
        }
        if(idx+T[idx]<=N){
            dfs(idx+T[idx],pay+P[idx]);
        }else{
            dfs(idx+T[idx],pay);
        }

        dfs(idx+1,pay);
    }
}