[JAVA]백준 2096번: 내려가기

www.acmicpc.net/problem/2096

2096번: 내려가기

 

1. 문제 설명

 

N 줄에 0 이상 9 이하의 숫자가 세 개씩 적혀있을 때 첫 줄에서 마지막 줄까지 내려가면서 얻을 수 있는 최대 점수, 최소 점수를 출력하는 문제이다.

 

내려가는 방법은 3가지가 있는데 아래 그림과 같다.

 

2. 풀이

 

메모리 제한이 있으나 신경 쓰지 않아도 풀 수 있는 문제이다.

 

[N][3] 크기의 max와 min 배열을 만든 후 가능한 값들을 하나씩 더해가면서 max와 min 배열을 채워나가면 되는 간단한 문제이다.

 

3. 코드

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    public static int N;


    public static void main(String[] args) throws IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

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

        int[][] min=new int[N][3];
        int[][] max=new int[N][3];


        for(int x=0;x<N;x++) {


            StringTokenizer st = new StringTokenizer(br.readLine());

            int one = Integer.parseInt(st.nextToken());
            int two = Integer.parseInt(st.nextToken());
            int three = Integer.parseInt(st.nextToken());

            if (x == 0) {
                min[0][0] = max[0][0] = one;
                min[0][1] = max[0][1] = two;
                min[0][2] = max[0][2] = three;
            } else {
                min[x][0] = Math.min(min[x - 1][0], min[x - 1][1]) + one;
                max[x][0] = Math.max(max[x - 1][0], max[x - 1][1]) + one;

                min[x][1] = Math.min(Math.min(min[x - 1][0], min[x - 1][1]), min[x - 1][2]) + two;
                max[x][1] = Math.max(Math.max(max[x - 1][0], max[x - 1][1]), max[x - 1][2]) + two;

                min[x][2] = Math.min(min[x - 1][1], min[x - 1][2]) + three;
                max[x][2] = Math.max(max[x - 1][1], max[x - 1][2]) + three;
            }
        }


        int answer_min=Math.min(Math.min(min[N-1][0],min[N-1][1]),min[N-1][2]);
        int answer_max=Math.max(Math.max(max[N-1][0],max[N-1][1]),max[N-1][2]);

        System.out.println(answer_max + " " + answer_min);





    }




}