[백준/Gold V] 내려가기 - 2096

[Gold V] 내려가기 - 2096

문제 링크

성능 요약

메모리: 50928 KB, 시간: 324 ms

분류

다이나믹 프로그래밍, 슬라이딩 윈도우

제출 일자

2024년 12월 5일 04:15:08

문제 설명

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

 

 

 

 

---

풀이 및 코드

다이나믹프로그래밍 방식으로 첫번째 행부터 각 행의 합을 계산하여 가장 마지막 행의 최소값, 최대값을 구하면 된다.

map[n][3] 에 대하여 최소 합을 저장하는 배열 min[n][3]과 최대 합을 저장하는 배열 max[n][3]가 있다고 가정하자

 

최소 값 합을 저장하는 배열 min의 i번째 행에서 각 열의 값은 다음과 같다.

min[i][0] = Math.min(min[i][0], min[i][1]) + map[i][0]
min[i][1] = Math.min(min[i][0], min[i][1], min[i][2]) + map[i][1]
min[i][2] = Math.min(min[i][1], min[i][2]) + map[i][2]

최대 값 합을 저장하는 배열 max의 i번째 행에서 각 열의 값은 다음과 같다.

max[i][0] = Math.max(max[i][0], max[i][1]) + map[i][0]
max[i][1] = Math.max(max[i][0], max[i][1], max[i][2]) + map[i][1]
max[i][2] = Math.max(max[i][1], max[i][2]) + map[i][2]

 

이후 max 배열에서 가장 마지막 행의 최대값과 min 배열에서 가장 마지막 행의 최소값을 출력한다.

 

위의 내용을 적용한 전체 풀이 코드

import java.io.*;
import java.util.*;

public class Main {
    private static int[][] map;
    private static int[][] min;
    private static int[][] max;

    // 다이나믹 프로그래밍 : 이전 행의 결과 값을 가지고 현재 행을 계산할 수 있음
    private static void dp(int n){
        for (int i = 1; i < n; i++){
            // 이전 행의 계산 값 중 작은 값과 현재 행을 더함
            min[i][0] = Math.min(min[i-1][0], min[i-1][1]) + map[i][0];
            min[i][1] = Math.min(min[i-1][0], Math.min(min[i-1][1], min[i-1][2])) + map[i][1];
            min[i][2] = Math.min(min[i-1][1], min[i-1][2]) + map[i][2];
            // 이전 행의 계산 값 중 큰 값과 현재 행을 더함
            max[i][0] = Math.max(max[i-1][0], max[i-1][1]) + map[i][0];
            max[i][1] = Math.max(max[i-1][0], Math.max(max[i-1][1], max[i-1][2])) + map[i][1];
            max[i][2] = Math.max(max[i-1][1], max[i-1][2]) + map[i][2];
        }
    }



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // min, max, map 배열 초기화
        min = new int[n][3];
        max = new int[n][3];
        map = new int[n][3];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            map[i][1] = Integer.parseInt(st.nextToken());
            map[i][2] = Integer.parseInt(st.nextToken());
        }
        br.close();
        // min, max 배열 첫번째 행 채워주기
        for (int i = 0; i < 3; i++) {
            min[0][i] = map[0][i];
            max[0][i] = map[0][i];
        }

        dp(n); // dp 실행

        // 결과 출력
        System.out.println(Math.max(Math.max(max[n-1][0], max[n-1][1]), max[n-1][2]) + " " + Math.min(Math.min(min[n-1][0], min[n-1][1]), min[n-1][2]));


    }
}