개요
[백준 14501]
https://www.acmicpc.net/problem/14501
상담에 필요한 소요시간이 퇴사일을 넘으면 안되며, 얻을 수 있는 최대 수익을 구해야 한다.
보기만 해도 어려워 보이는 해당 문제는 직접 풀어도 어렵다...
많은 시도를 해봤으며 결국 능력 내에서 해결을 하지 못해서 지피티와 구글링을 통해서 문제를 해결하였다.
⭐️ Dynamic Programming(DP - 동적 프로그래밍) 이란 무엇인가?
위 문제를 쉽게 해결하기 위해서는 동적 프로그래밍 기법을 알아야 한다.
동적 프로그래밍이란 복잡한 문제를 하위 문제로 잘게 쪼개어 문제에 접근하는 방식이다.
DP를 적용시킬 수 있는 조건은 아래와 같다.
-
중복되는 부분 문제(Overlapping Subproblems) : 문제를 해결하기 위해 동일한 하위 문제를 여러 번 해결해야 하는 경우가 존재한다. 동적 프로그래밍은 이 중복을 줄이기 위해 결과를 저장하고 재사용한다.
-
최적 부분 구조(Optimal Substructure) : 문제를 해결하는 과정에서 큰 문제를 작은 문제의 최적 해결 방식으로 분할할 수 있어야 한다. 즉, 전체 문제의 최적 해결 방법은 그 부분 문제들의 최적 해결 방법들로 구성된다는 특징이 있다.
💡 문제에 어떻게 적용해야 할까?
하위 문제로 쪼개기 위해 특정 날짜부터 퇴사일까지 가능한 최대 급여를 계산하여 배열에 저장한다.
-
문제를 해결하는 과정에서 큰 문제를 작은 문제의 최적 해결 방식으로 분할할 수 있어야 한다. 즉, 전체 문제의 최적 해결 방법은 그 부분 문제들의 최적 해결 방법들로 구성된다는 특징이 있다.
-
이를 위해 각 날짜에 대해 그날을 시작으로 끝내는 상담을 했을 때 얻을 수 있는 최대 급여를 구하여, 이를 저장한 dp[] 배열을 활용한다.
for (int i = quit_day; i >= 1; i--) {
if (i + time[i] <= quit_day + 1) {
dp[i] = Math.max(dp[i + 1], wage[i] + dp[i + time[i]]);
} else {
dp[i] = dp[i + 1];
}
}
i번째 날에 일을 시작했을 때, 퇴사일이 넘지 않으면 일을 할 수 있고, 일을 하는 경우와 하지 않는 경우를 비교하여 dp 에 저장해야 한다.
최종적으로는 첫 번째 날부터 시작할 때 얻을 수 있는 최대 급여는 1번째 인덱스에 값이 저장되어 있다.
🔧 알고리즘 작성
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 퇴사일
int quit_day = Integer.parseInt(br.readLine());
// 시간과 급여 배열
int[] time = new int[quit_day + 1];
int[] wage = new int[quit_day + 1];
int[] dp = new int[quit_day + 2]; // dp 배열 (퇴사일까지 얻을 수 있는 최대 급여)
// 입력 처리
for (int i = 1; i <= quit_day; i++) {
String[] input = br.readLine().split(" ");
time[i] = Integer.parseInt(input[0]);
wage[i] = Integer.parseInt(input[1]);
}
// 역순으로 계산 (퇴사일 이전부터 시작)
for (int i = quit_day; i >= 1; i--) {
// 일을 끝낼 수 있는 날이 퇴사일을 넘지 않으면, 해당 일을 할 수 있음
if (i + time[i] <= quit_day + 1) {
dp[i] = Math.max(dp[i + 1], wage[i] + dp[i + time[i]]);
} else {
dp[i] = dp[i + 1]; // 일을 할 수 없으면 그 날의 최대 급여는 그대로
}
}
bw.write(dp[1] + "\n");
br.close();
bw.flush();
bw.close();
}
}해당 코드로 정답을 얻을 수 있었다.
그러나 해당 문제는 절반 이상이 구글링과 지피티로 푼 문제이므로 DP 개념이 사용된 다른 문제를 추가로 풀어보고자 한다.
참고 자료
https://velog.io/@boyeon_jeong/동적계획법Dynamic-Programming
https://hongjw1938.tistory.com/47
