📙[Algo] 24.05.03 알고리즘

알고리즘 문제) BOJ 2096. 내려가기

• 링크 : https://www.acmicpc.net/problem/2096

문제 요약

• N줄에 0이상 9이하의 숫자가 세 개씩 적혀 있다.
• 첫 줄에서 시작해서 마지막 줄까지 내려가기 게임을 하는데, 제약 조건에 따라 내려가야 한다.
  • 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동이 가능하다.
• 이 때, 얻을 수 있는 최대 점수와 최소 점수 구하기
  • 점수는 위치한 곳의 수의 합

시간 제한

• 1초

입력

• N
  • 1 ≤ N ≤ 10만
• N개의 줄에 숫자가 세 개씩 주어진다
  • 0~9 중 하나가 된다.

출력

• 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력

접근법

• 직관적으로 풀었다.
  • 인접한 곳만 이동할 수 있다고 해서 경계체크하며, 열(col)-1, col+1, col 이렇게 세가지 경우로 재귀 호출했다.
  • 만약 도착지까지 도달했다면(row ≥ N) 도착했으므로 return 0해주고(애초에 경계 ), 재귀할 때마다 현재 위치 비용을 ret변수에 더해주었다.
  • 이걸 max값, min값 각각 함수를 만들어서 호출했다.

코드

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

public class Main {
    static int N;
    static int[][] arr;
    static int[][] dpMax;
    static int[][] dpMin;
    static int max;
    static int min = 1 << 30;

    static int recurMax(int row, int col) {

        if (row >= N) return 0;

        if (dpMax[row][col] != -1) return dpMax[row][col];

        int retMax = 0;
        if (col - 1 >= 0) {
            retMax = Math.max(recurMax(row + 1, col - 1) + arr[row][col], retMax);
        }

        if (col + 1 < 3) {
            retMax = Math.max(recurMax(row + 1, col + 1) + arr[row][col], retMax);
        }

        retMax = Math.max(recurMax(row + 1, col) + arr[row][col], retMax);

        dpMax[row][col] = retMax;
        return dpMax[row][col];
    }

    static int recurMin(int row, int col) {

        if (row >= N) return 0;

        if (dpMin[row][col] != -1) return dpMin[row][col];

        int retMin = 1 << 30;
        if (col - 1 >= 0) {
            retMin = Math.min(recurMin(row + 1, col - 1) + arr[row][col], retMin);
        }

        if (col + 1 < 3) {
            retMin = Math.min(recurMin(row + 1, col + 1) + arr[row][col], retMin);
        }

        retMin = Math.min(recurMin(row + 1, col) + arr[row][col], retMin);

        dpMin[row][col] = retMin;
        return dpMin[row][col];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        arr = new int[N][3];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dpMax = new int[N][3];
        dpMin = new int[N][3];

        for (int[] ints : dpMax) {
            Arrays.fill(ints, -1);
        }

        for (int[] ints : dpMin) {
            Arrays.fill(ints, -1);
        }

        for (int i = 0; i < 3; i++) {
            max = Math.max(max, recurMax(0, i));
            min = Math.min(min, recurMin(0, i));
        }

        bw.write(max + " " + min);
        bw.flush();
        bw.close();
        br.close();
    }
}