[ 문제 ]

[ 구현 ]
잘 모르겠어서 gpt한테 힌트달라고 했는데도 점화식 이해하는데 좀 애먹었다..
힌트보고 이해한 다음에 코드는 손수 짰는데, 배열 크기 관련해서 신경써줘야하는 부분이 좀 있어서 디버깅하면서 고쳤다.
dp[i] = 시각 i부터 N까지 시작할 때 얻을 수 있는 최대 거리 (이때 지침 지수는 0)로 잡고
누적합을 통해 필요한 구간의 합을 계산하였다.
이때 필요한 구간의 합이란 연속으로 달릴 구간을 의미한다(i ~ i + L - 1)
dp자체가 bottom-up 방식이 아니라 top-down 방식으로 내려가는 형식이며
L이 가지는 제한 조건 -> L <= (n - i + 1) / 2를 반영해주면 된다.(끝날때 지침 지수가 0이려면 구간의 절반을 넘게 달릴 순 없음)
최종적으로 핵심이 되는 점화식은
dp[i] = Math.max(dp[i+1], sum(i ~ i + L - 1) + dp[i+2L])이다.
우선 dp[i+1]은 이전까지 구했던 값이 더 큰 경우 현상유지를 위한 기본 코드이며
i부터 시작해서 L만큼 달렸을때의 거리를 누적합을 통해 O(1)을 통해 계산하였다.
추가적으로 2L의 의미는 L 구간만큼 연속으로 달리면 다시 L구간만큼 쉬어줘야하기 때문에 그 부분이 반영되었다.
다만 L값이 증가함에 따라 값이 바뀌는 부분도 기록을 해줘야하기 때문에 Math.max(dp[i], ...)를 한번 더 감싸주었다.
+) 또한 dp[i + 2 * j]에서 인덱스가 n + 1까지 도달하는 경우 발생하기 때문에 arrayIndexOutOfBoundError가 터질 수 있어, 크기를 의도적으로 n + 2로 잡아주었다.
[ 코드 ]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// dp[i] = 시각 i부터 N까지 시작할 때 얻을 수 있는 최대 거리 (이때 지침 지수는 0)
public class Main {
static int[] dp;
static int n, m;
static int[] dist;
static int[] prefixDist;
static int answer;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static void readInput() throws IOException{
String input = br.readLine();
String[] arr = input.split(" ");
n = Integer.parseInt(arr[0]);
m = Integer.parseInt(arr[1]);
dist = new int[n + 2];
prefixDist = new int[n + 1];
dp = new int[n + 2];
for (int i = 1; i <= n; i++) {
input = br.readLine();
dist[i] = Integer.parseInt(input);
prefixDist[i] = prefixDist[i - 1] + dist[i];
}
}
private static void dp() {
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= (n - i + 1) / 2; j++) {
// i부터 L거리만큼 연속으로 달린 경우 거리 계산(누적합 배열을 이용해 N(1)으로)
int distSum = prefixDist[n] - prefixDist[i - 1] - (prefixDist[n] - prefixDist[i + j - 1]);
dp[i] = Math.max(dp[i], Math.max(dp[i + 1], distSum + dp[i + 2 * j]));
}
}
answer = dp[1];
}
private static void solution() throws IOException {
readInput();
dp();
System.out.println(answer);
}
public static void main(String[] args) throws IOException {
Main.solution();
}
}
[ 마무리 및 느낀 점 ]
개인적으로 골드4이지만 간단히 풀기는 어려운 느낌의 dp인 것 같다.
dp 관련해서 좀 더 공부를 하고 다양한 케이스를 접하며 기본 이해도를 높여야겠다.
같은 문제를 2차원 dp, 3차원 dp로 풀 수 있는 것 같던데 한번 시도해볼 예정이다.
'Algorithm > 백준' 카테고리의 다른 글
| [백준/java] 25515번 - 트리 노드 합의 최댓값 (0) | 2025.10.30 |
|---|---|
| [백준/java] 14499번 - 주사위 굴리기 (1) | 2025.09.26 |
| [백준/java] 14502번 - 연구소 (2) | 2025.08.17 |
| [백준/java] 2539번 - 모자이크 (3) | 2025.08.14 |
| [백준/c++] 31230번 - 모비스터디 (0) | 2024.02.20 |