백준 1932번 : 정수 삼각형 java

이 문제는 다이나믹 프로그래밍을 이용하여 이전의 최선의 경우의 수를 배열에 저장하며 푸는 문제입니다.

코드를 보면서 이 문제를 설명해드리겠습니다.

---

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

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[][] intArr = new int[n][];

        for(int i = 1; i<=n; i++)
            intArr[i-1] = new int[i];

        for(int i = 0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j = 0; j<i+1; j++)
                intArr[i][j] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i<n; i++){
            for(int j = 0; j<i+1; j++){
                if(j == 0)
                    intArr[i][j] += intArr[i-1][j];
                else if(j == i)
                    intArr[i][j] += intArr[i-1][j-1];
                else
                    intArr[i][j] += Math.max(intArr[i-1][j], intArr[i-1][j-1]);
            }
        }

        int max = Integer.MIN_VALUE;

        for(int i = 0; i<n; i++)
            max = Math.max(max, intArr[n-1][i]);

        System.out.println(max);
    }
}

저는 이 문제를 intArr에 처음에는 입력받은 값들을 넣었다가 반복문을 통해서 이전에 있던 값들 중에서 최선의 결과에
도달하게 문제를 풀었습니다.

그림을 통해서 알고리즘을 설명드리겠습니다.

예제 1번을 문제대로 표현한 그림입니다.

문제에서는 값을 입력할 때 왼쪽 대각선에 있는 수를 바로 아래에, 오른쪽 대각선에 있는 수를 우측 하단에 두었습니다.

이 그림을 배열에 들어가 있는 모양대로 보기 편하게 바꿔보도록 하겠습니다.

이와 같은 모양이 됩니다.

따라서 우리는 문제의 조건인 대각선에 있는 것만 선택할 수 있다고 할 때 배열상에서는 바로 아래에 있는 수 또는 우측 하단에 있는 수를 선택할 수 있습니다.

예를 들어 빨간색 블럭이 수를 선택할 때 주황색 블록만 선택할 수 있습니다.

	for(int i = 1; i<n; i++){
            for(int j = 0; j<i+1; j++){
                if(j == 0)
                    intArr[i][j] += intArr[i-1][j];
                else if(j == i)
                    intArr[i][j] += intArr[i-1][j-1];
                else
                    intArr[i][j] += Math.max(intArr[i-1][j], intArr[i-1][j-1]);
            }
        }

이 코드는 그것을 나타낸 코드입니다. j가 0일 때이나 j == i일 때를 따로 신경 써 준 이유는 j가 0일 때 j-1의 값을
불러올 수 없기 때문이고 j == i일 때도 마찬가지로 범위를 넘어가서 값을 불러올 수 없기 때문입니다.