[백준 / JAVA] 1932번 정수 삼각형

이 글에는 백준 1932번 정수 삼각형 문제에 대한 풀이와 정답 코드(JAVA)가 있습니다.

 

문제

정수의 값이 들어오는 높이가 N인 삼각형이 있다.

이 삼각형의 맨 위층부터 시작해서 대각선 왼쪽 또는 오른쪽에 있는 것중에서 숫자를 선택해서 최대가 되는 경로를 구하는 프로그램을 작성

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

1 ≤ N ≤ 500

0 ≤ 삼각형을 구성하는 점수 ≤ 9999

 

풀이

• DP를 이용해서 최댓값 구하기
• 높이 500이고 각 점수가 9999이므로 int 범위에서 해결 가능
• 입력을 받을 때 index out of bounds 에러를 방지하기 위해서 한칸 띄우고 입력받기

기본적인 접근법은 현재 내 위치 arr[i][j] 라고 한다면 arr[i-1][j-1] 과 arr[i-1][j] 의 값을 비교해서

더 큰 값과 내 위치의 값을 더해주면 항상 최댓값을 만드는 경로를 구할 수 있다.

 

 

위의 그림에서 왼쪽과 같이 0열은 비워주고 받아야 index out of bounds 에러를 피할 수 있다.

아래로 내려가면서 두개의 값을 비교해서 더 큰값과 현재 나의 값을 더해주고

마지막 행을 sort 하면 dp[N-1][N] 값이 최댓값이 된다.

 

왼쪽 그림의 노란색으로 표현 된 곳에서 7이 현재 위치라고 한다면

8 위치까지의 최댓값과 1위치까지의 최댓값을 비교해서 그 값과 나를 더해주면 된다.

 

 

다음과 같은 핵심코드를 통해 DP를 접근하면 된다.

dp[0][1] = triangle[0][1];
int c = 2; //삼각형을 돌기 위한 index

for (int i = 1; i < N; i++) {
    for (int j = 1; j <= c; j++) {
        int max_value = Math.max(dp[i-1][j-1], dp[i-1][j]);
        dp[i][j] = max_value + triangle[i][j];
    }
    c++; 
}

Arrays.sort(dp[N-1]);

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_1932_정수삼각형 {
    static int N;
    static int[][] triangle;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        triangle = new int[N][N+1]; //index에러 방지
        StringTokenizer st = null;
        for (int i = 0; i < N; i++) {
             st = new StringTokenizer(br.readLine());
             int c = 1;

             while(st.hasMoreTokens()) {
                 triangle[i][c++] = Integer.parseInt(st.nextToken());
             }
        }//end input

        int answer = get_max(triangle);
        System.out.println(answer);

    }
    private static int get_max(int[][] triangle) {
        int[][] dp = new int[N][N+1];

        dp[0][1] = triangle[0][1];
        int c = 2; //삼각형을 돌기 위한 index

        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= c; j++) {
                int max_value = Math.max(dp[i-1][j-1], dp[i-1][j]);
                dp[i][j] = max_value + triangle[i][j];
            }
            c++;
        }

        Arrays.sort(dp[N-1]);
        return dp[N-1][N];
    }
}

1932번: 정수 삼각형

1932번: 정수 삼각형