[BOJ] 14501 : 퇴사 - java

문제

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

---

문제풀이

이 문제는 주어진 기간 동안 여러 상담 일정을 조정하여 얻을 수 있는 최대 수익을 계산하는 문제입니다. 각 상담은 특정 기간이 소요되며, 그 기간 동안 다른 상담을 진행할 수 없습니다. 목표는 상담 일정을 최적화하여 가능한 최대 수익을 얻는 것입니다.
동적 프로그래밍(DP)을 사용하여 각 날에 얻을 수 있는 최대 수익을 이전 날의 최대 수익과 비교하여 점진적으로 계산합니다.
특정 날 i 에 상담을 수행할 수 있는 경우 상담을 진행하여 얻는 수익을 고려하여 해당 상담이 끝나는 날(i + t[i])에 최대 수익을 갱신

---

소스코드

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

public class _14501 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] t = new int[N];
        int[] p = new int[N];
        int[] maxP = new int[N + 1];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            if (i + t[i] <= N) {
                maxP[i + t[i]] = Math.max(maxP[i + t[i]], maxP[i] + p[i]);
            }
            maxP[i + 1] = Math.max(maxP[i + 1], maxP[i]);
        }

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

---

etc

알고리즘 분류 : 다이나믹 프로그래밍, 브루트포스 알고리즘

https://djun95.tistory.com/25

다이나믹 프로그래밍

 

https://djun95.tistory.com/12

브루트포스 탐색 알고리즘