[백준 *Java] - 정수 삼각형 (1932)

 

정수 삼각형 문제보기

1932번: 정수 삼각형

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

문제 설명
위 그림은 크키가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서, 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때,
이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라.
아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 
삼각형을 이루고 있는 각 수는 모두 정수이며, 
범위는 0 이상 9999 이하이다.

입력
첫째 줄에 삼각형의 크기 n( 1 <= n <= 500)이 주어지고, 둘째 줄부터 n+1 번째 줄까지 정수 삼각형이 주어진다.

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

---

👇 접근방식

삼각형을 일단 직각 삼각형으로 생각해서 2차배열을 이용해서 풀 생각입니다.

이 문제는 범위가 크지 않으니, 반복문을 활용하고 일단 맨위층부터 탐색합니다.

층마다 입력한 값에 주어진 길이만큼 모든 경우의 최대값을 찾습니다.

그리고 마지막 층에서 최대갓값을 가지는 수를 출력합니다.

---

 

아래는 성공한 코드입니다.

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

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

        int N = Integer.parseInt(br.readLine());
        DP = new int[N+1][N+1];

        StringTokenizer st;
        for(int i = 1; i <= N; i++) {
            int j = 1;
            st = new StringTokenizer(br.readLine());

            while(j <= i && st.hasMoreElements()) {
                int num = Integer.parseInt(st.nextToken());

                if(j == 1) DP[i][j] = DP[i-1][j] + num;
                else if(j == i) DP[i][j] = DP[i-1][j-1] + num;
                else DP[i][j] = Math.max(DP[i-1][j-1], DP[i-1][j])+num;

                j++;
            }
        }

        int max = 0;
        for(int num : DP[N]) max = Math.max(max, num);

        System.out.println(max);
    }
}

 

 

두 번째 방법

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

public class Boj_1932_2 {
    static int DP [][];
    static int arr [][];
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int H = Integer.parseInt(br.readLine());
        DP = new int[H][H];
        arr = new int[H][H];

        // 2차원 배열에 직각삼각형을 x, y 사각 테이블 표에 담는다고 생각합니다.
        StringTokenizer st;
        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                //System.out.println(arr[i][j]);
            }
        }
        // 제일 윗값 초기화
        DP[0][0] = arr[0][0];

        // 하나 씩 DP 세팅    
        for (int i = 1; i < H; i++) {
            for (int j = 0; j <= i; j++) {
                if (j > 0) {
                    DP[i][j] = DP[i-1][j-1] + arr[i][j];
                }

                DP[i][j] = Math.max(DP[i][j], DP[i-1][j] + arr[i][j]);
            }
        }

        // 층간 최대값 구하기
        int max = DP[H-1][0];
        for (int i = 1; i < H; i++) {
            max = Math.max(max, DP[H-1][i]);
        }

        System.out.println(max);
    }
}