[백준] 2096번 - 내려가기 java

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번까지 내려갈 때 인접한 곳으로만 이동 가능합니다.

baekjoon

위 그림을 볼 경우 

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]));

---

코드 설계하기

1. N의 크기를 입력받습니다. 동시에 minDP[][], maxDP[][]배열을 초기화해줍니다.
2. 첫 번째 각 위치에서의 점수를 각각 저장합니다.
   • minDP [0][0] = a, minDP [0][1] = b, minDP [0][2] = c
   • maxDP [0][0] = a, maxDP [0][1] = b, maxDP [0][2] = c
3. 점화식을 사용하여 각 dp[][]를 채웁니다.
4. 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;
    }
}