[이코테][Java] 정수 삼각형

문제 설명

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

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 or 대각선 오른쪽에 있는 것 중에서만 선택할 수 있습니다.

 

입력조건

• 첫째 줄에 삼각형의 크기
• 둘째 줄부터 n+1번째 줄까지 정수 삼각형

출력조건

• 합이 최대가 되는 경로에 있는 수의 합

입출력 예시

입력예시	출력예시
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5	4

 

 

 

 

문제 풀이

• 다이나믹 프로그래밍으로 풀이
• '금광' 문제와 비슷한 유형의 문제이다.
• 정수삼각형의 수들을 배열에 저장하면, 윗층에서 현재 위치로 내려올 수 있는 경우는 2가지가 있다.(왼쪽 위 or 바로 위)
• 이 두가지 경우 중에서 더 큰  값을 가지는 경우를 선택해서 현재 위치의 수와 합한다.
• 점화식으로 나타내면 다음과 같다.

d[i][j] = d[i][j] + max(d[i-1][j-1], d[i-1][j])

 

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));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());    //삼각형의 크기

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

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                int left, right;
                //왼쪽 위
                if (j == 1) {
                    left = 0;
                } else {
                    left = dp[i - 1][j - 1];
                }
                //바로 위
                if (j == i) {
                    right = 0;
                } else {
                    right = dp[i - 1][j];
                }
                dp[i][j] = dp[i][j] + Math.max(left, right);
            }
        }

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

        System.out.println(result);
    }
}

---

 

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈