백준: 15486번 (퇴사 2) [JAVA]

문제 링크

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

15486번: 퇴사 2

풀이

전체적인 풀이 과정은 다음과 같다.

1. 각 날짜 속 상담 소요일과 금액을 저장할 배열과 dp용 배열을 생성
   
2. 전체 요일 N을 받아 배열 초기화, 그리고 전체 N번에 걸쳐 각 날짜 상담의 소요일과 금액을 받아 저장
3. 첫째날부터 N번째 날까지 계산 반복
   1) 현재 요일의 상담 누적값과 이전 날의 상담 누적값 중 더 큰 값을 비교해 현재값에 저장
   2) 이전 날의 상담 누적값 + 오늘자 상담의 금액을 오늘 진행한 상담이 끝나는 요일에 저장(비교 후 저장)
4. dp 배열 속 최종 요일값을 출력

 문제에 주어진 조건 중 전체 일수에 해당하는 N이 상당히 크기 때문에(최대 1,500,000), dp를 활용해 최대한 탐색을 줄여야 한다. 전체 주어진 상담의 일정과 금액을 비교해 최대로 금액을 많이 받을 수 있는 날을 선정해야 한다. 특정일 기준으로, 현재에서 할 수 있는 연산은 우선 이전날 기준으로 상담 최대값과 오늘자 상담을 진행했을 때 받을 수 있는 금액을 합하여, 오늘 시작한 상담이 끝나는 날짜로 총금액을 저장하는 연산을 할 수 있다. 물론 중복되는 날짜들이 있을 수 있기 때문에 총금액을 저장하기 전 기존 값과 비교해 최대값을 저장해야 한다. 그리고 나서는 오늘자에 대한 최대값을 계산하기 위해선, 앞선 연산으로 저장된 오늘자의 상담 최대 누적금액과 이전날의 상담 최대 누적 금액을 비교해 그 중 최대값을 저장하면 이것이 기준으로 삼은 날에 대한 상담 최대 누적금액이 된다.

 

public class Main {
    static int[][] schedule;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        schedule = new int[N + 1][2];
        dp = new int[N + 1];

        for (int i = 1; i <= N; i++) {//해당 날짜 상담의 소요일과 금액 저장
            String[] tAndP = br.readLine().split(" ");
            schedule[i][0] = Integer.parseInt(tAndP[0]);
            schedule[i][1] = Integer.parseInt(tAndP[1]);
        }

        for (int i = 1; i <= N; i++) {//첫날부터 마지막날까지
            int time = schedule[i][0], price = schedule[i][1];

            if (i + time - 1 <= N) {//이전날 누적값에 오늘 상담을 더한 값을 해당 날에 대입
                dp[i + time - 1] = Math.max(dp[i + time - 1], dp[i - 1] + price);
            }
            
            dp[i] = Math.max(dp[i], dp[i - 1]);//이전 날과 오늘 중 더 큰 금액 저장
        }

        System.out.println(dp[N]);
    }
}

결과