[백준 15486] 퇴사 2 (JAVA)

백준 15486번 문제 - 퇴사 2

15486번: 퇴사 2

---

문제 분석

• 퇴사를 N일 앞두고 있어, 남은 기간동안 최대로 많은 페이를 벌고 싶다.
• 스케줄이 주어졌을 때 벌 수 있는 최대 페이를 출력해라.

---

문제 풀이 방식

•  

 

1. 일당 페이 계산 후 최대 수익 구하기

• 받은 상담 정보들의 일당페이를 계산한 후, 일당페이가 큰 값(퇴사 전에 끝나는)부터 일을 하기로 결정 !
• 하기로 결정했으면 -> 해당 수일동안은 일을 못하도록 check ArrayList의 해당 일을 true로
  (check ArrayList : 이미 일이 부여된 날짜인지 확인)
  --> 이 방식은 테스트 실행 결과 런타임 에러 (IllegalArgument)] 발생 ...

 

2. DP를 써야겠다 생각

• DP : 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말.
• 알겠는데 해당 문제에서 어떻게 적용해야 할지 모르겠다.

---

해결 키 포인트

 

• DP 사용 문제
  • [해당 작업을 했을 때, 끝나는 날에 pay] , [현재 받을 수 있는 최대 pay]+[현재 상담 pay] 
    중 누가 더 페이가 많은 지 확인
• dp array 크기를 N+1 로 설정 !
  • 마지막 날에 만약 T=1일 경우 일을 할 수 있기 때문에 +1까지 확인해줘야한다.

 

+ 해설에서 헷갈렸던 부분 !

입력 for문하고 최대값 찾는 for문을 따로 뒀다. 왜 따로뒀지?
위에 N+1까지 확인해야되서 인 것으로 판별, 그럼 그냥 입력하고 최대값 찾는 것 같이 해도 무관할 거라 판단 !
같이 해도 무관 ! 대신 마지막날 근무를 따로 한번 더 확인해줌!

---

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 남은 일 수
        int N = Integer.parseInt(br.readLine());

        // dp 값
        int [] dp = new int[N+1];

        // 최대 수익
        int max = 0;

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            // N일에 따른 상담 일정 입력
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());

            // max보다 현재 dp값이 클 경우 변경
            if(max < dp[i])
                max = dp[i];

            // dp 값 설정
            if (t+i < N + 1) {
                dp[t+i] = Math.max(dp[t+i], max + p);
            }
        }

        // 마지막 날도 근무 했을 수도 있으니 확인
        if(max < dp[N])
            max = dp[N];

        System.out.println(max);
    }

}