[백준 1932] 정수 삼각형(JAVA)

백준 1932번 문제 -  정수 삼각형

1932번: 정수 삼각형

---

문제 분석 

 

 

• 삼각형을 이루게 숫자가 주어진다.
• 아래층에 있는 수: 현재 층에서 선택된 수의 대각선 왼쪽, 대각선 오른쪽에 있는 것 중에서만 선택
• 이때 첫번째 층 부터 마지막 층까지 거쳐간 수를 모두 더했을 때, 가장 큰 수를 출력해라.

 

---

해결 포인트

 

• DP 이용
• 각 층마다 숫자 등록
  • i층에 j번째 수(nums[i][j])의 왼쪽 대각선은 i+1층에 j번째 수(nums[i+1][j]),
    오른쪽 대각선은 i+1층에 j+1번째 수(nums[i+1][j+1])로 한다.
• 1층인 하나의 수는 값 넣어놓기
• 다음 층부터는 dp로 가장 큰 값 구하기
  • nums[i][j]가 갈 수 있는 다음 값 
    1. nums[i+1][j]
    2. nums[i+1][j+1]
  • 이 곳의 저장된 합과 현재 층에서 넘어갔을 때 합 중 큰 값을 저장

 

---

코드

 

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

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

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

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

        int [][] sums = new int[N][N];
        sums[0][0] = nums[0][0];
        for (int i = 0; i < N-1; i++) {
            for (int j = 0; j < i+1; j++) {
                sums[i+1][j] = Math.max(sums[i][j] + nums[i+1][j], sums[i+1][j]);
                sums[i+1][j+1] = Math.max(sums[i][j] + nums[i+1][j+1], sums[i+1][j+1]);

            }
        }

        int result = 0;
        for (int i = 0; i < N; i++) {
            result = Math.max(result, sums[N-1][i]);
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }

}