[백준 알고리즘] 1932번(숫자 삼각형) - DP 문제

백준 알고리즘

요즘에 많은 기업에서 알고리즘 시험을 보는 것 같습니다.

카카오도 그렇고 다른 기업들도 S/W 분야는 인적성 대신 알고리즘 시험을 치는 것 같습니다.

그래서 오늘도 꾸준히 문제를 풀어보도록 하겠습니다.

전과 같은 DP 문제 입니다. 

  문제

  해설

문제는 쉽게 이해를 하실 수 있을 겁니다. 

제일 위에서 부터 제일 아래까지 내려가면서 자기 자식을 더해서 가장 큰 값을 구하는 문제입니다. 

i 가 1 ->3으로 갈 때까지 최고 합을 구하면 되는 것입니다.

경우의 수를 보게 되면 ABD / ABE / ACE / ACF 이렇게 4가지가 있습니다.

ABF가 안되는 이유는 당연히 문제에 대각선 왼/오른쪽(자식) 중 선택하라고 했으므로

F는 C의 자식이지 B의 자식이 아니기 때문에 당연히 안됩니다.

간략하게 배열에 맞게 숫자를 넣어봤습니다. 그럼 이제 하나씩 더해 보도록 하겠습니다.

빨강 테두리 부분과 파랑 테두리 부분을 먼저 보겠습니다.

이 부분의 합을 구하는 방법은 딱 하나 밖에 없습니다. 

예를 들어 (3 , 1)까지 더한 값을 구하기 위해선 (3, 1) + (1 , 1) + (2 , 1)  이렇게 밖에 하지 못합니다.

(4 , 1)은 (3 , 1)까지 더한 값에 (4 , 1)까지 더한 값이 되겠습니다.

그리고 파랑 테두리 부분은 (4 , 4)를 구하기 위해선 (1 , 1) + (2 , 2) + (3 , 3) + (4 , 4) 가 됩니다.

그렇다면 (i , j)라고 바꾼다면 

빨강 테두리는 j의 값은 변하지 않고 1로 고정되어 있으며 파랑 테두리는 i 와 j의 값이 같습니다.

이것을 통해 하나의 식을 구할 수 있습니다. 이렇게요

또한 여기서 알아야 할 것이 더한 값을 그 배열 안에 저장시킨다는 것입니다.

if( i == 1)
    list[i][j] = list[i-1][j] + list[i][j];

위에 것은 빨간 테두리에 값을 구하는 것입니다. (2 , 1) = (1 , 1) + (2 , 1) 이 됩니다.

(2 , 1)까지 더한 값을 (2 , 1)에 저장시키는 것입니다.

if( i == j)
    list[i][j] = list[i-1][j-1] + list[i][j];

위에 것은 빨간 테두리에 값을 구하는 것입니다. (2 , 2) = (1 , 1) + (2 , 2) 이 됩니다.

(2 , 2)까지 더한 값을 (2 , 2)에 저장시키는 것입니다.

그리고  중간에 것을 구하기 위해선 비교가 필요합니다. 

우리가 (3 , 2) 값 까지 더하려면 (2 , 1) / (2 , 2) 둘 값을 비교하여 더 큰 값과 합을 구해야합니다. 

아래와 같이 식을 구할 수 있겠습니다.

else{
    list[i][j] = Math.max(list[i-1][j-1] , list[i-1][j]) + list[i][j];

위에 것은 빨간 테두리에 값을 구하는 것입니다  

(3 , 2) = Math.max((2 , 1) , (2 , 2)) + (3 , 2)가 되겠습니다.

  코드

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