https://www.acmicpc.net/problem/2096
난이도 : G5
Tag : DP
풀이 일자 : 2025-03-10
문제 탐색하기
N: 줄 개수 (1 <= N <= 100,000)
- 각 줄마다 3의 숫자(0<= 점수 <= 9)가 주어진다.
- 1번 줄에서 N번줄까지 이동하며 점수가 누적
이동 규칙:
- 현재 위치에서 아래 인접한 칸으로만 이동 가능
- 즉, (i, 0) → (i+1, 0 or 1), (i, 1) → (i+1, 0 or 1 or 2), (i, 2) → (i+1, 1 or 2)
위 규칙을 만족하면서 N 번 줄까지 내려올 때의 최대 점수와 최소 점수를 구하는 게 핵심
가능한 시간복잡도
브루트포스(완전탐색)으로 풀 경우 O(3^n)이 걸립니다.
이때 최대 N이 100,000이므로 절대 불가능합니다. 17만 되어도 1억이 넘어버리기 때문이죠.
DP로 풀 경우 O(N)이기때문에 O(100,000)내에서 안정적으로 동작 가능합니다.
알고리즘 선택
DP를 선택하겠습니다.
이전에 푼 RGB거리 문제와 유사합니다.
2025.03.09 - [Algorithm/Baekjoon] - [백준] 1149번 - RGB거리 java
1번부터 n번까지 내려갈 때 인접한 곳으로만 이동 가능합니다.
위 그림을 볼 경우
1번째 1번의 위치에서는 2번째의 1,2번으로
1번째 2번의 위치에서는 2번째의 1,2,3번으로
1번째 3번의 위치에서는 2번째의 2,3번으로 이동 가능합니다.
즉, 아래처럼 점화식을 세울 수 있습니다.
특히 이번 문제는 최대 최소를 따로 구해야 하므로 최대를 구하는 dp와 최소를 구하는 dp를 따로 만들어줍니다.
//a:첫번째 위치 점수, b:두번째 위치 점수, c:세번째 위치 점수
//현재 최대 점수 = 이전에 가능한 위치 중 최대 점수 + 현재 점수
maxDP[i][0] = Math.max(maxDP[i - 1][0], maxDP[i - 1][1]) + a;
maxDP[i][1] = Math.max(maxDP[i - 1][0], Math.max(maxDP[i - 1][1], maxDP[i - 1][2])) + b;
maxDP[i][2] = Math.max(maxDP[i - 1][1], maxDP[i - 1][2]) + c;
//현재 최소 점수 = 이전에 가능한 위치 중 최소 점수 + 현재 점수
minDP[i][0] = Math.min(minDP[i - 1][0], minDP[i - 1][1]) + a;
minDP[i][1] = Math.min(minDP[i - 1][0], Math.min(minDP[i - 1][1], minDP[i - 1][2])) + b;
minDP[i][2] = Math.min(minDP[i - 1][1], minDP[i - 1][2]) + c;
기저사례
이제 초기값을 구해보겠습니다.
처음 위치에서 점수를 선택할 때는 이전 위치의 영향을 받지 않습니다.
그러므로 각각 점수를 초기화해 줍니다.
final static int MAX_SIZE = 3;
for (int j = 0; j < MAX_SIZE; j++) {
maxDP[0][j] = minDP[0][j] = read();
}
이후 모든 dp값이 구해졌을 때 마지막 위치에서 최대, 최소 점수를 각각 골라주면 됩니다.
int maxAns = Math.max(maxDP[n-1][0], Math.max(maxDP[n-1][1], maxDP[n-1][2]));
int minAns = Math.min(minDP[n-1][0], Math.min(minDP[n-1][1], minDP[n-1][2]));
코드 설계하기
- N의 크기를 입력받습니다. 동시에 minDP[][], maxDP[][]배열을 초기화해줍니다.
- 첫 번째 각 위치에서의 점수를 각각 저장합니다.
- minDP [0][0] = a, minDP [0][1] = b, minDP [0][2] = c
- maxDP [0][0] = a, maxDP [0][1] = b, maxDP [0][2] = c
- 점화식을 사용하여 각 dp[][]를 채웁니다.
- DP에 저장된 값을 각각 확인 후 최대 최소 비용을 출력합니다.
회차 별 수정사항
1회 차 :
점화식을 잘못 작성했다.
코드가 많아서 숫자를 적을 때 실수를 한 것 같다.
코드 수정 후 올바르게 알고리즘이 동작하였다.
실수한 코드
maxDP[i][1] = Math.max(maxDP[i-1][1], Math.max(maxDP[i-1][0], maxDP[i-1][2])) + info[i][1];
수정된 코드
maxDP[i][1] = Math.max(maxDP[i-1][1], Math.max(maxDP[i-1][0], maxDP[i-1][1])) + info[i][1];
2회 차:
통과했지만 메모리와 시간을 더 줄일 수 있을 거라고 생각했다.
BufferedReader + StringTokenizer로 입력받던 방식을 System.in.read()를 사용하도록 변경했다.
또한, 원래 info[][]에 값을 따로 저장했으나, 바로 DP 배열에 저장하도록 변경했다.
//수정 전
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[][] info = new int[n][MAX_SIZE];
int[][] maxDP = new int[n][MAX_SIZE];
int[][] minDP = new int[n][MAX_SIZE];
for(int i=0; i<n; i++){
st = new StringTokenizer(br.readLine());
for(int j=0; j<MAX_SIZE; j++){
info[i][j] = Integer.parseInt(st.nextToken());
}
}
maxDP[0][0] = info[0][0];
maxDP[0][1] = info[0][1];
maxDP[0][2] = info[0][2];
minDP[0][0] = info[0][0];
minDP[0][1] = info[0][1];
minDP[0][2] = info[0][2];
for(int i=1; i<n; i++){
// DP사용
}
//결과 출력
}
}
//수정 후
public static void main(String[] args) throws Exception {
int n = read();
int[][] maxDP = new int[n][MAX_SIZE];
int[][] minDP = new int[n][MAX_SIZE];
for (int j = 0; j < MAX_SIZE; j++) {
maxDP[0][j] = minDP[0][j] = read();
}
for (int i = 1; i < n; i++) {
int a = read(), b = read(), c = read();
// DP사용
}
//결과 출력
}
static int read() throws Exception {
int c, n = System.in.read() & 15;
while ((c = System.in.read()) > 32)
n = (n << 3) + (n << 1) + (c & 15);
return n;
}
}
메모리와 시간이 절반 가까이 줄었다!
정답코드
import java.io.*;
class Main {
final static int MAX_SIZE = 3;
public static void main(String[] args) throws Exception {
int n = read();
int[][] maxDP = new int[n][MAX_SIZE];
int[][] minDP = new int[n][MAX_SIZE];
for (int j = 0; j < MAX_SIZE; j++) {
maxDP[0][j] = minDP[0][j] = read();
}
for (int i = 1; i < n; i++) {
int a = read(), b = read(), c = read();
maxDP[i][0] = Math.max(maxDP[i - 1][0], maxDP[i - 1][1]) + a;
maxDP[i][1] = Math.max(maxDP[i - 1][0], Math.max(maxDP[i - 1][1], maxDP[i - 1][2])) + b;
maxDP[i][2] = Math.max(maxDP[i - 1][1], maxDP[i - 1][2]) + c;
minDP[i][0] = Math.min(minDP[i - 1][0], minDP[i - 1][1]) + a;
minDP[i][1] = Math.min(minDP[i - 1][0], Math.min(minDP[i - 1][1], minDP[i - 1][2])) + b;
minDP[i][2] = Math.min(minDP[i - 1][1], minDP[i - 1][2]) + c;
}
int maxAns = Math.max(maxDP[n-1][0], Math.max(maxDP[n-1][1], maxDP[n-1][2]));
int minAns = Math.min(minDP[n-1][0], Math.min(minDP[n-1][1], minDP[n-1][2]));
System.out.println(maxAns +" "+ minAns);
}
static int read() throws Exception {
int c, n = System.in.read() & 15;
while ((c = System.in.read()) > 32)
n = (n << 3) + (n << 1) + (c & 15);
return n;
}
}
'Algorithm > Baekjoon' 카테고리의 다른 글
[백준] 2503번 - 숫자 야구 java (0) | 2025.03.12 |
---|---|
[백준] 13567번 - 로봇 java (0) | 2025.03.11 |
[백준] 1149번 - RGB거리 java (0) | 2025.03.09 |
[백준] 14430번 - 자원 캐기 java (0) | 2025.03.08 |
[백준] 9095번 - 1, 2, 3 더하기 java (0) | 2025.03.07 |