백준 1932 정수 삼각형 자바

1932 정수 삼각형 문제 보러가기

1932번: 정수 삼각형

문제 설명

자바 코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int point[][] = new int[n][n];
        int maxPoint[][] = new int[n][n];
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            StringTokenizer strTok = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j <= i; j++) {
                point[i][j] = Integer.parseInt(strTok.nextToken());
            }
        }
        maxPoint[0][0] = point[0][0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0)
                    maxPoint[i][j] = maxPoint[i - 1][j] + point[i][j];
                else if (j == i)
                    maxPoint[i][j] = maxPoint[i - 1][j - 1] + point[i][j];
                else
                    maxPoint[i][j] = Integer.max(maxPoint[i - 1][j - 1], maxPoint[i - 1][j]) + point[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            result = Integer.max(result, maxPoint[n - 1][i]);
        }
        System.out.print(result);
    }
}

문제 풀이

 밑에는 입력값                   최대값 경로                                             배열순서 로 되어 있습니다.

1레벨     7                                7                                                      00
2레벨    3 8                       3+7     8+7                                             10  11
3레벨   8 1 0             8+(3+7)    1+(8+7)    0+(8+7)                           20  21  22
4레벨  2 7 4 4   2+(8+(3+7))  5+(8+(3+7))  4+(1+(8+7))  4+(0+(8+7))    30  31  32  33

이렇게 적어보니 최대값을 구하는 식은 현재 레벨의 첫번째 ,중간단계, 마지막번째 이렇게 3가지로 나누어집니다.

코드를 적으면 다음과 같습니다.

if (j == 0) maxPoint[i][j] = maxPoint[i - 1][j] + point[i][j]; //첫번째
else if (j == i) maxPoint[i][j] = maxPoint[i - 1][j - 1] + point[i][j];//마지막
else maxPoint[i][j] = Integer.max(maxPoint[i - 1][j - 1], maxPoint[i - 1][j]) + point[i][j];//중간

동적프로그래밍으로 결과값을 저장하여 마지막 레벨중 가장 큰 결과값을 출력하여 풀었습니다.