[Java] 백준 15486번 : 퇴사2

문제소개

해결과정

총 두 번의 시도를 통해 해결했다.

DP를 활용해 풀이했으며, 첫 번째 풀이는 1일차부터 N일차까지 순서대로 해당 날짜에 총 소요되는 일 수를 더한 위치에 기존에 있던 값과 누적합을 비교해 더 큰 값으로 갱신해주는 방식으로 진행했다.

 

하지만 특정 날짜를 건너뛰고 다른 상담을 처리하는 것이 더 많은 금액을 받을 수 있다.

또한 그런 상황이라면, 해당 인덱스의 dp배열에는 기존의 값이 존재하지 않기 때문에(= 0) 잘못된 연산 결과를 얻게됐다.

 

따라서 기존의 로직에, 바로 직전 dp배열의 인덱스를 먼저 현재 인덱스의 dp배열로 받아와주는 코드를 한줄 추가해 문제를 해결했다.

솔루션

package DP.백준15486_퇴사2;

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

public class Main {

    static int N;
    static int dp[];

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

        N = Integer.parseInt(br.readLine());
        dp = new int[N + 2];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int T = Integer.parseInt(st.nextToken());
            int P = Integer.parseInt(st.nextToken());
            try {
                dp[i] = Math.max(dp[i - 1], dp[i]);
                dp[i + T] = Math.max(dp[i + T], dp[i] + P);
            } catch (ArrayIndexOutOfBoundsException e) {}
        }
        int result = Arrays.stream(dp)
                .max()
                .orElse(0);

        System.out.println(result);

    }
}