[JAVA] 백준 q15486 - 퇴사2

15486번: 퇴사 2

---

> 의식의 흐름
dfs로 풀면되려나..? > 실패
반복문 사용해서 i번째 날까지의 최대 수익을 구하자 > 성공

> 풀이 과정
1. 퇴사까지 남은 일수(N)를 입력 받는다.
2. Consulting 클래스에 상담에 대한 정보를 담아 배열(consultings)에 담는다.
- Consulting 클래스에 date(필요한 일수), cost(받을 수 있는 돈)을 담는다.
3. i일까지의 최대 수익을 이용하여 i일의 상담을 끝내고 얼마 받을 수 있는지 배열(profit)에 계속 업데이트한다.

for(int i=0;i<N;i++){
    maxProfit = Math.max(maxProfit, profit[i]); // i일까지의 최대 수익

    int nextDate = i + consultings[i].date; // 상담 끝나는 날짜(1일~N일)
    if(nextDate<=N){ // 퇴사 전에 끝나는 상담일 경우
        profit[nextDate] = Math.max(profit[nextDate], maxProfit+consultings[i].cost);
    }
}

 

4. profit에서 최대 값을 출력한다.

 

> 코드

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

public class Main {
    public static int N; // 남은 일수
    public static Consulting[] consultings;
    public static int[] profit;

    public static class Consulting{
        int date;
        int cost;

        public Consulting(int date, int cost){
            this.date = date;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        consultings = new Consulting[N];
        profit = new int[N+1];
        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            consultings[i] = new Consulting(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }

        int maxProfit = 0;
        for(int i=0;i<N;i++){
            maxProfit = Math.max(maxProfit, profit[i]); // i일까지의 최대 수익

            int nextDate = i + consultings[i].date; // 상담 끝나는 날짜(1일~N일)
            if(nextDate<=N){ // 퇴사 전에 끝나는 상담일 경우
                profit[nextDate] = Math.max(profit[nextDate], maxProfit+consultings[i].cost);
            }
        }

        for(int i=0;i<=N;i++){
            maxProfit = Math.max(maxProfit, profit[i]);
        }

        bw.write(Integer.toString(maxProfit));
        bw.flush();

        br.close();
        bw.close();
    }
}