[BOJ-1932] 정수 삼각형(JAVA)

백준 1932 정수 삼각형

 

1932번: 정수 삼각형

 

문제 설명

 

 - 맨 위층 부터 시작하여, 아래에 있는 수 중 하나를 선택하여 아래층으로 내려온다.

 

 - 이제까지 선택한 수의 합이 최대가 되는 값을 구하라.

 

 - 아래층으로 내려올 때 현재 층에 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것만 선택할 수 있다.

 

 - 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력하라.

---

 

입력 값

 

 - 첫째 줄에 삼각형의 크기 n(1 <= n <= 500)이 주어진다.

 

 - 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

 

 - 삼각형을 이루고 있는 수는 모두 0이상 9999이하의 정수이다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 맨 위층 부터 합이 하나씩 선택하여 층을 하나씩 옮겨 가며 가장 큰 값을 저장하면 된다.

 

 - 예를 들어, 가장 위층을 7층이라고 하면,

   7층의 값을 바탕으로 6층에 올 수 있는 값들을 저장한다.

   그 다음, 6층의 값을 바탕으로 5층에 올 수 있는 값들을 저장한다.

 

 - 이 방식으로 하면, 해당 층의 값들은 한 번씩만 방문하면 되기 때문에 O($N^2$)의 시간복잡도가 걸린다.

 

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/1932
// 정수 삼각형
public class Main {

    private static int boards[][] = new int[502][502];

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

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

        int N = Integer.parseInt(bf.readLine());

        for(int i=1;i<=N;i++){
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for(int j=1;j<=i;j++){
                boards[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        for(int i=1;i<=N;i++){
            for(int j=1;j<=i;j++){
                boards[i][j]+=Integer.max(boards[i-1][j],boards[i-1][j-1]);
            }
        }

        int result=0;

        for(int i=1;i<=N;i++){
            result = Integer.max(result,boards[N][i]);
        }

        System.out.println(result);

    }
}