[BOJ - JAVA] 1932 - 정수 삼각형(다이나믹 프로그래밍)

# 주소

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

1932번: 정수 삼각형

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        
        int[][] arr = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i+1; j++){
                arr[i][j] = scan.nextInt();
            }
        }
        int sum = arr[0][0];
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i+1; j++){
            	if(j == 0)
            		arr[i][j] += arr[i-1][j];
            	else if(j == i)
            		arr[i][j] += arr[i-1][j-1];
            	else
            		arr[i][j] += Math.max(arr[i-1][j-1], arr[i-1][j]);
            	sum = Math.max(sum,  arr[i][j]);
            }
            
        }
        
        System.out.println(sum)

이 블로그의 첫 다이나믹 프로그래밍 문제입니다.(DP)

dp를 잘 풀려면 우선 점화식의 개념을 잘 알고 있어야 하는데, 주로 Math.max, Math.min가 자주 이용됩니다.

우선 arr[i][j]를 Scanner를 통해 입력받습니다.

그리고 sum을 (일명 합계) arr[0][0]으로 저장했는데, 이유는 다음 for문에서 계산을 좀 더 빠르게 하기 위함입니다.

이후 이중 for문으로 들어가 i = 1부터, j = 0부터인데 i+1까지 범위로 지정합니다. 왜냐하면 코딩 처음 배울 때 별로 삼각형 그리는거 기억하시나요?? 그 원리랑 이 문제가 똑같습니다. *로 삼각형 그리기라고 생각하면 수월합니다!

그리고 이제부터 1) j == 0일 때는 왼쪽의 대각선 끝을 뜻합니다. 따라서 arr에 값을 저장할 것입니다. j == 0일 땐 바로 위 칸의 arr를 받아서 더하면 되므로 저렇게 작성합니다. 2) i == j 일 땐 오른쪽 대각선 끝을 뜻합니다. 따라서 arr[i][j]에 j-1크기의 값을 저장하면 되겠습니다. 그리고 3) 그 외의 경우에는 정수삼각형의 몸통부분이 되겠습니다. 이 부분은 dp으로 풀어야 합니다! 

그러므로 arr[i][j]에 그 이전의 i-1행에서 j-1열의 값을 더하는 것이 큰지, j열의 값을 더하는 것이 큰지를 Math.max를 이용해 구한 뒤 sum에 저장합니다

이때 sum에서도 기존의 sum과 arr[i][j]을 비교해서 최종적으로 sum 을 출력하면 되겠습니다.