[백준/Java] 1932: 정수 삼각형

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

 

---

 

문제 설명

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

위는 크기가 5인 정수 삼각형

맨 위층에 있는 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구해야 함

아래층으로 내려갈 땐 현재 층에서 선택한 수의 왼쪽 대각선 또는 오른쪽 대각선에 위치한 것들 중에서만 고를 수 있음

 

 

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500),
둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어짐

 

출력

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

 

---

 

풀이

맨 위에서 아래로 내려가기엔 어떤 경로가 가장 큰 합을 낼지 알 수 없으므로 아래에서 위로 올라가며 계산

다이나믹 프로그래밍(DP)을 사용하여 각 수의 합을 저장할 2차원 배열을 따로 생성

 

1. 입력되는 정수를 저장할 2차원 배열 triangle 생성
2. 각 수의 합을 저장할 2차원 배열 dp 생성
   1. 이때 dp의 마지막 행은 triangle의 마지막 행과 동일 - 밑에서부터 더해나갈 것이기 때문
3. dp를 아래부터 채워나감
   
   1. 현재 위치가 dp[i][j]일 때, 아래 층에서 왼쪽 대각선 수(dp[i + 1][j]), 오른쪽 대각선 수(dp[i + 1][j + 1]) 확인
   2. 두 개의 수 중 더 큰 수를 찾아 triangle[i][j]과 합산
   3. 그 수를 dp[i][j]에 저장
   4. 한 층이 다 채워지면 위 층으로 올라가 위 과정 반복
4. dp[0][0]에 가장 큰 합이 저장됨

 

코드

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

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

        int n = Integer.parseInt(br.readLine());
        int[][] triangle = new int[n][n];   // 정수 삼각형 저장
        int[][] dp = new int[n][n];         // 숫자의 합 저장

        // 삼각형 초기화
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int length = 0;
            while(st.hasMoreTokens()){
                triangle[i][length++] = Integer.parseInt(st.nextToken());
            }
        }

        // dp의 마지막 행 = triangle의 마지막 행
        System.arraycopy(triangle[n - 1], 0, dp[n - 1], 0, n);

        // dp를 아래부터 채우기
        // dp[n-1]은 채워져있으므로 dp[n-2]부터 시작
        for (int i = n - 2; i >= 0; i--) {
            // 삼각형은 각 층마다 정수의 개수가 다르므로 for문은 i층에 맞춰 i번만 반복
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }

        System.out.println(dp[0][0]);
    }
}

 

---

 

참고

• https://st-lab.tistory.com/131