[자바] 백준 1932번 정수 삼각형 2021-06-17

일단 매우 어려웠다. 그나마 이거 풀기 전, 2차원 배열의 DP를 활용하는 문제인 1149번 RGB 거리 문제를 풀지도 못하고, 정답을 한번 봐서 그런지, 접근법은 대충 맞았다. 그러나, 진짜 이런 2차원 배열의 DP활용 문제를 처음 봤더라면 접근조차 못했을 것이다.

 

우선 가장 핵심적인 아이디어는 "아래로 내려갈수록, 가장 최대의 값만 선택하면 안된다. 즉, 그리디로 풀수 없다." -> 그렇기에 모든 경우의 수를 다 따져야 된다.-> 처음부터 아래로 내려가는 규칙을 찾자. 이다.

노트에 그려 보면 맨 왼쪽노드와 맨 오른쪽 노드는 바로 그전 계층의 노드값을 그대로 받는다.

->

if(j==0){
dp[i][j]=arr[i][j]+dp[i-1][0];
}
if(j==i-1){
dp[i][j]=arr[i][j]+dp[i-1][j];
}

만약 이 두경우가 아닐시에는 두가지 선택지가 있다. 바로 그 전 계층의(n-1) 같은 인덱스 값과 +1한 인덱스 값이 저장된 dp에서 큰 값을 받는 것이다.

*DP문제에서 가장 중요한 것은 DP배열의 인덱스가 과연 무엇을 의미하는지 정확하게 아는것 이다. 나는 여기서 DP[i][j] 는

(0,0)부터 (i,j)번째 배열값 까지의 경로까지 이동했다고 했을때, 나올수있는 가장 최대값

이라고 정의했다.

 

그리고 주어진 모든 DP[i][j]의 값 중 최댓값을 출력하면 된다.(사실 엄밀히 말하자면 맨 마지막 계층 의 값들중 최댓값이다. 왜냐하면 결국 끝까지 이동하면 맨 마지막으로 방문하는 노드는 마지막 계층일 것이므로, 위 예시로 든다면 4 5 2 6 5 의 DP값중 가장큰 것)

import java.util.Scanner;

public class Main {


    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n=s.nextInt();
        int[][] arr=new int[n][n];
        int[][] dp=new int[n][n];
        int cnt=1;
        for (int i = 0; i < n; i++) {
            for(int j=0;j<=i;j++){
                arr[i][j]=s.nextInt();
            }


        }
        dp[0][0]=arr[0][0];
        int max=Integer.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            for(int j=0;j<=i;j++){
                if(j==0){
                    dp[i][j]=dp[i-1][0]+arr[i][j];

                }
                else if(j==i){
                    dp[i][j]=dp[i-1][j-1]+arr[i][j];
                }
                else{
                    dp[i][j]=Math.max(dp[i-1][j-1],dp[i-1][j])+arr[i][j];
                }
                max=max>dp[i][j]?max:dp[i][j];
            }
        }
        System.out.println(max);


        }
    }

 

오늘 2차원 배열을 이용한 DP문제를 처음 접했는데, 많이 당황스럽기도 했고,어려웠지만

마지막에 도달하는 순서인 N번째항에 집중해서 규칙성을 찾는것.

이 중요한 사실이라는 것을 알게 되었다.

하루가 다르게 알고리즘 실력이 느는거 같아 기분이 좋다.ㅎㅎㅎ