[백준 18290, Java] 퇴사

문제

www.acmicpc.net/problem/14501

14501번: 퇴사

 

풀이

"오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다."라는 조건을 생각해보면, 백준이가 퇴사를 하기 위해서는 백준이의 상담이 N번째 되는 날 안에 끝나야 한다는 말이된다. 

 

상담을 하는 날을 정한다는 행위가 반복된다. 이 때 상담을 하는 날은, 이전 상담 종료일 이후부터 N번째 날이 된다. 다시말해 상담을 하는 날을 정하려면 이전 상담 종료일을 알아야 한다. 따라서 재귀함수의 매개변수로 "이전 상담 종료일"을 넘긴다. 그러면 재귀함수는 "이전 상담 종료일"을 기준으로 N보다 클 때와 작을 때로 나눌 수 있다.

 

 이전 상담 종료일이 N보다 큰 경우, 백준이가 N+1부터 회사에 없기 때문에 불가능 하다. 이전 상담 종료일이 N보다 작거나 같은경우 다음 상담 가능한 날짜는 이전 상담 종료일 +1일 부터 N번쨰 날까지이다.

 

 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

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

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

        T[0] = 0;
        P[0] = 0;

        for(int day = 1; day<=N; day++){
            st = new StringTokenizer(br.readLine()," ");
            int t = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());

            T[day] = t;
            P[day] = p;
        }

        int result = getMax(0,0);
        bw.write(String.valueOf(result));
        bw.flush();
    }

    static int getMax(int finishDay, int paySum){
        if(finishDay >N){
            return 0;
        }
        else{
            int max = paySum;


            //nextDay : 다음 가능한 상담날짜
            //nextFinishDay : nextDay에 상담을 하고 끝난 날짜
            for(int nextDay = finishDay+1; nextDay<=N; nextDay++){
                int nextFinishDay = nextDay + T [nextDay] -1;
                int payment = P[nextDay];

                int result = getMax(nextFinishDay, paySum + payment);
                max = Math.max(max, result);
            }

            return max;
        }
    }

}