[백준] 🥇 15486 퇴사 2

📌 난이도

🥇 Gold 5

📌 문제

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

📌 풀이

어제 DP문제에 엄청 고민을 하고, DP 문제가 어떤 형식인지 어떤 방법으로 접근을 해야 하는지, 깨달음을 얻어서 그런가, 골드문제임에도 불구하고 매우 쉽게 풀렸다.

일단 날짜와 돈을 arr에 집어넣었고, dp는 0으로 전부 초기화 해주었다.

for문으로 처음부터 끝까지 돌린다고 하자, 이때 n번째일때, dp[n]은 지금까지 들어온 dp값(이후 설명)과 이전 값을 비교하여, 더 큰 값을 넣는다.
이후 가장 중요한 부분인데, arr[n][0](상담에 걸리는 시간) + 현재 Index의 주소값에 있는 dp값에 현재 dp[n] + arr[n][1]를 Math.max로 더 큰 값으로 초기화 해준다.
이런식으로 반복문을 돌리면 결국 각 dp에 있는 값은 항상 최대값이 된다.

DP 문제를 풀면서 느낀점은 어떻게 해야지 dp에 있는 값이 항상 그 지점의 최대값/최소값이 될 수 있는지에 대해 고민하고, 그에 대한 점화식을 찾아내는 것이 중요하다는 것을 느꼇다.

문제를 풀면 풀수록 실력이 확확 느는 느낌이라 요즘 공부하는 맛이 난다. 😎

📌 Code

package DP;

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

public class N15486 {
    public static int[][] arr;
    public static int[] dp;
    static int target;

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

        Arrays.fill(dp, 0);

        StringTokenizer st;
        arr[0][0] = 0;
        arr[0][1] = 0;
        for (int i = 1; i < target + 1; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        for (int i = 1; i < target + 2; i++) {
            MakeDP(i);
        }

        System.out.println(dp[target + 1]);
    }

    public static void MakeDP(int index) {
        dp[index] = Math.max(dp[index], dp[index - 1]);
        if (index + arr[index][0] <= target + 1) {
            dp[index + arr[index][0]] = Math.max(arr[index][1] + dp[index], dp[index + arr[index][0]]);
        }
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁