[boj] 백준 14501 퇴사 (Java) - 완전탐색

[문제]

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

 

[풀이]

경우는 2가지이다.

1. 상담을 하는 경우. 그날의 비용과 그 다음 할 수 있는 상담일로 이동한다.

2. 상담을 하지 않는 경우. 비용 합은 그대로이고, 다음 날로 이동한다.

 

상담일이 n일을 벗어나면 안되기 때문에 범위를 체크해준 후 dfs를 호출했다. 

 

[코드]

 

package 브루트포스;

import java.util.*;
import java.io.*;

public class boj_14501_퇴사 {
    static int n;
    static int[] ti;
    static int[] pi;
    static int answer = -1;
    public static void main(String[] args) throws Exception{
        //백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        ti = new int[n];
        pi = new int[n];
        StringTokenizer st;
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken()); //기간
            int p = Integer.parseInt(st.nextToken()); //비용
            
            ti[i] = t;
            pi[i] = p;
        }

        dfs(0, 0);

        System.out.println(answer);

    }

    public static void dfs(int now, int sum){
        if(now==n){
            //종료조건. 마지막 날까지 탐색
            answer = Math.max(answer, sum);
            return;
        }

        //상담을 하는 경우
        if(now+ti[now]<=n)
            dfs(now+ti[now], sum+pi[now]);

        //상담을 안하는 경우
        if(now+1<=n) dfs(now+1, sum);
        
        return;
    }
    
}