[Java] 백준(실버-1) 1932번 - 정수 삼각형

문제 풀이

---

이번 문제는 동적 계획법 DP를 이용해 풀 수 있는 문제이다.

아이디어 도출

이번에는 재귀가 아닌 반복문을 활용한 Bottom-Up 방식으로 풀었다.

문제풀이를 위한 과정을 살펴보자면, 정수 삼각형의 꼭대기부터 아래로 내려가면서 누적합을 구해가는데 최하단 층까지 누적합을 구했다면, 최하단 층에서 가장 큰 최댓값을 구하면 된다.

점화식 세우기

그렇다면 이제, 동적 계획법을 이용한 DP 점화식을 세워보자.

아래 층으로 내려가면서 선택된 수는 대각선 왼쪽 위, 대각선 오른쪽 위의 수들 중 더 큰 값을 선택하게 된다. 이를 문제에 접근하기 위한 인덱스로 표현하자면 다음과 같다.

• 대각선 왼쪽 위(i-1, j-1)
• 대각선 오른쪽 위(i-1, j)

결국, 삼각형의 아래 층으로 내려가면서(탐색) 현재 층의 수는 대각선 왼쪽 위, 오른쪽 수중 큰수와 현재 층의 수인 현재값을 더해가면서 갱신해가면 되는 것이다! 이를 토대로 D[i][j] = (i, j)에 도착했을 때 누적합의 최댓값을 구해야 한다고 보면 된다.

점화식: DP[i][j] = max(D[i-1][j-1], D[i-1][j]) + triangle[i][j]

이 점화식을 토대로 정수 삼각형을 탐색하며 DP 테이블을 갱신한 뒤, DP 테이블의 최하층에 누적합 중 가장 큰 값을 출력하면 된다.

1. 정수 삼각형의 크기만큼 순회하며, DP 점화식을 통해 DP 테이블에 누적합을 갱신한다.
2. 이때, 대각선 왼쪽 위, 오른쪽 위중 큰 값 + 현재값을 DP 테이블의 현재값으로 갱신한다.
3. DP 테이블 갱신이 모두 끝나면, 최하단 층 누적합에서 최대값을 출력한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    // DP 테이블 선언
    static int[][] D;

    // 정수 삼각형 배열 선언
    static int[][] triangle;

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

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
                
                // 1. 정수 삼각형의 꼭대기부터 아래로 내려가면서 값을 누적해가며, 최하층에서 최댓값을 구해야 한다.
                // 2. DP 테이블의 최하단 층에 정수 삼각형의 선택지를 통한 최댓값을 누적하여 갱신한다.
                // 3. DP 테이블의 최하단 층까지 갱신이 완료되면, 최하단 층에서 최댓값을 구한다.

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

                triangle = new int[N+1][N+1];
                D = new int[N+1][N+1];

                // 정수 삼각형 배열을 입력받는다.
                for(int i=1; i<=N; i++) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    for(int j=1; j<=i; j++) {
                        triangle[i][j] = Integer.parseInt(st.nextToken());
                    }
                }

                /**
                 * DP 테이블 갱신
                 * 점화식: 대각선 왼쪽 위(i-1, j-1), 대각선 오른쪽 위(i-1, j) 중 큰 값 + 현재값
                 * D[i][j] = max(D[i-1][j-1], D[i-1][j]) + triangle[i][j]
                 */
                for(int i=1; i<=N; i++) {
                    for(int j=1; j<=i; j++) {
                        D[i][j] = Math.max(D[i-1][j-1], D[i-1][j]) + triangle[i][j];
                    }
                }

                // DP 테이블의 최하층에서 최댓값을 구한다.
                int max = 0;
                for(int i=1; i<=N; i++) {
                    if(max < D[N][i]) {
                        max = D[N][i];
                    }
                }
                bw.write(max+"\n");
                
        }

    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.