백준 1932번 정수 삼각형JAVA 구현해보기

---

```

백준 1932번 정수 삼각형 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1. 백준 1932번 풀이

---

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

1932번: 정수 삼각형

 

백준 1932번 정수 삼각형은

 

 

난이도 실버 등급의 문제로서

 

아래와 같은 입력을 받을 경우

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

 

첫줄에 숫자는 삼각형의 높이입니다.

삼각형의 꼭대기인 두 번째 줄부터 각 층에 위치한 삼각형의 수들이 주어진다고 가정할 때

꼭대기에서 바닥까지 한층에 인접한 하나의 수만 경유해서 얻을 수 있는 최댓값을 구해주면 되는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

삼각형의 정보를 배열 형식으로 입력을 받고

findMaxPathSum()이라는 함수를 만들어서

삼각형을 경유하는 최대 값을 구해줍니다.

 

findMaxPathSum에 각 층마다(i) 열을 돌면서(j)

경우의 수들을 dp [i][j]에 넣어두고

각 층을 돌면서 구한 값들의 최댓값을 retval에 넣은 다음에 반환합니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int triangleDepth = Integer.parseInt(br.readLine());
        int[][] dp = new int[triangleDepth][triangleDepth];
        for (int i = 0; i < triangleDepth; i++) {
            final String[] inputs = br.readLine().split(" ");
            final int inputLen = inputs.length;
            for (int j = 0; j < inputLen; j++) {
                dp[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        // 연산 및 출력
        System.out.print(findMaxPathSum(dp));
    }

    public static int findMaxPathSum(int[][] dp) {
        int retVal = dp[0][0];
        final int triangleDepth = dp.length;

        for (int i = 1; i < triangleDepth; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    dp[i][j] += dp[i - 1][j];
                } else if (j == i) {
                    dp[i][j] += dp[i - 1][j - 1];
                } else {
                    dp[i][j] += Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
                }
                retVal = Math.max(retVal, dp[i][j]);
            }
        }

        return retVal;
    }
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---