1932 - 정수 삼각형[S1]

 

문제

https://www.acmicpc.net/problem/1932

 

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

풀이

전형적인 배열 형태의 DP 사용을 고려하였으나, 비슷한 방식을 사용하였다.

바닥 피라미드부터 가지치기를 수행하여 가장 최대값을 적용해 나가는 것.

결국 맨 위층까지 올라가면 최대의 경로를 자연스럽게 구할 수 있다.

자세한 내용은 코드를 참조할 것.

코드

 

//https://www.acmicpc.net/problem/1932

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

/*
2차월 배열 n*n 역시 사용가능하지만(N < 500),
그래프로 직접 해결하였다.
 */

public class Main {
    static int N;
    static int[] dp;
    static List<List<Integer>> pyramid = new ArrayList<>(); //피라미드
    public static void main(String[] args) throws Exception {
        input();
        int roofValue = pyramid.get(0).get(0); //최상위 값
        if(N == 1) { //한 층만 존재
            System.out.println(roofValue);
            return;
        }
        //바닥 층수부터 정상 - 1 칸까지 진행
        for(int i = 0; i < N - 1; i++) {
            check(N - (i + 1));
        }

        int maxValue = Math.max(pyramid.get(1).get(0), pyramid.get(1).get(1)); //바닥부터 N - 1층까지 쌓인 최대 값
        System.out.println(roofValue + maxValue);
    }
    static void check(int level) {
        List<Integer> now = pyramid.get(level);      //현재 층
        List<Integer> next = pyramid.get(level - 1); //윗 층
        int L = now.size();

        for(int i = 0; i < L - 1; i++) {
            next.set(i, next.get(i) + Math.max(now.get(i), now.get(i + 1)));
        }
    }

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < N; i++) {
            List<Integer> nowLevel = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreElements()) nowLevel.add(Integer.parseInt(st.nextToken()));
            pyramid.add(nowLevel);
        }
    }
}