[PG] 정수삼각형 - Java

[원문링크]

https://adorable-aspen-d23.notion.site/PG-6b703aa604e64d19a8b75904ba71d2fc

[PG] 정수삼각형

코딩테스트 연습 - 정수 삼각형

코딩테스트 연습 - 정수 삼각형

[풀이]

• 처음에 dfs로 했는데 시간초과났다! (dp카테고리에 잇는 거라서 무조건 날 줄 알긴했는데, dfs로 풀고 그거를 top-down으로 바꾸려고 그냥 풀어봄)
• 근데 바꾸려니까 완전 헷갈리기.. top-down으로 바꿀 때 제대로 이해 못하고 결국 구글링해서 살짜쿵 참고해서 풀었다.
• 다 풀고 bottom-up으로 다들 풀었길래 풀어봤는데 와 완전 직관적이고 세상 쉬움 앞으로는 아래에서부터 채우는 것도 생각해보자구!!

1. Top-down
   • 루트부터 시작해서 가지치기로 끝까지 내려갔다가 아래 레벨부터 차례로 갱신하면서 최종적으로 루트까지 다시 갱신하는 방법
   • 이해가 당연히 안갈것이다. 아래의 그림을 참고해보자
   • 왼쪽은 이 문제에서 주어준 트리의 모양이다. 코드에서는 BottomUp(row,col) 함수로 구성해놓았음
   • 함수의 호출 순서는 오른쪽 그림과 같다. 쪼오금 많이 복잡해도.. 숫자 따라서 읽어보면 이해가 될 수도..? 안되면 따라 그려보자.
   1. 파란색을 따라서 루트부터 가지치면서 내려간다. 그리고 리프노드
      1. (마지막 레벨을 만나면 리턴한다.)

      if(row >= N-1){
          dp[row][col] = triangle[row][col]; //마지막 애는 아무것도 안하고 그냥 그 값 리턴해줘야 함
          return dp[row][col];
      }
      

   2. 예를 들어서 노드 1→2→4→7→(4)→8→(4) 이 끝나고 나면, 노드4의 모든 인접 정점 탐색(가지치기)가 끝났으므로 4의 갱신이 이루어진다. 그리고 dp[2][0]에 그 연산 완료된 값이 저장되면 된다.

dp[row][col] = 0; //방문했다는 표시, 굳이 안해도 되는 것 같긴함
int ret = 0; //top-down 방식의 dp에서 그 포인트 아래로의 쭈루쭉쭉 연산이 모두 끝났을 때 return값

for(int i=0;i<2;i++){
    int newRow = row+1;
    int newCol = col + dCol[i];
    if(0<=newCol && newCol<triangle[newRow].length){
        ret = Math.max(ret, TopDown(newRow,newCol,triangle) + triangle[row][col]); //아래로 뻗쳐나가는 가지 중에서 가장 최댓값을 취해야 하므로 max연산을 해줌, 가지값+내꺼랑 비교한당
    }
}
return dp[row][col] = ret; //연산이 끝남, 리턴해줌

3. 방문순서 19 다음에 노드 5로 가게 되면 그 밑에 5→8→(5)→9→(5갱신)이 중복으로 일어나게 된다. 따라서 중복을 없애기 위해 dp[2][1]이 존재하면 이미 갱신이 완료된 애이므로 또 안하고 바로 리턴시키는 로직 추가

if(dp[row][col]!=-1){ //dp저장된값이 있다는 것은 리턴이 이미 완료되었다는 뜻이므로
    return dp[row][col];
}

 

[코드]

import java.util.*;

public class Pg_정수삼각형 {
    static int[][] triangle = {{7},{3,8},{8,1,0},{2,7,4,4},{4,5,2,6,5}};
    static int answer;
    static int N;
    static int[] dCol = {0,1};
    static int[][] dp;

    public static void main(String[] args) throws Exception{
        answer = 0;
        N = triangle.length;
        dp = new int[triangle.length+1][triangle.length+1];
        for(int[] arr:dp){
            Arrays.fill(arr,-1);
        }

        //끝까지 가야하니까 dfs로 푸는 것이군 -> 근데 시간초과 남, 중간에 저장할 수 있는 dp로 풀자
        //answer = TopDown(0,0, triangle);
        answer = BottomUp(triangle);
        System.out.println(answer);
    }

    static int BottomUp(int[][] triangle){
        //root가 아니라 아래에서부터 채워준다.
        for(int i=0;i<N;i++){ //제일 아래 값 채워주기
            dp[N-1][i] = triangle[N-1][i];
        }
        for(int i=N-2;i>=0;i--){
            for(int j=0;j<=i;j++){
                dp[i][j] = Math.max(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j];
            }
        }
        return dp[0][0];
    }

    static int TopDown(int row,int col, int[][] triangle){
        if(row >= N-1){
            dp[row][col] = triangle[row][col]; //마지막 애는 아무것도 안하고 그냥 그 값 리턴해줘야 함
            return dp[row][col];
        }

        if(dp[row][col]!=-1){ //dp저장된값이 있다는 것은 리턴이 이미 완료되었다는 뜻이므로
            return dp[row][col];
        }

        dp[row][col] = 0; //방문했다는 표시
        int ret = 0; //top-down 방식의 dp에서 그 포인트 아래로의 쭈루쭉쭉 연산이 모두 끝났을 때 return값

        for(int i=0;i<2;i++){
            int newRow = row+1;
            int newCol = col + dCol[i];
            if(0<=newCol && newCol<triangle[newRow].length){
                ret = Math.max(ret, TopDown(newRow,newCol,triangle) + triangle[row][col]); //아래로 뻗쳐나가는 가지 중에서 가장 최댓값을 취해야 하므로 max연산을 해줌, 가지값+내꺼랑 비교한당
            }
        }
        return dp[row][col] = ret; //연산이 끝남, 리턴해줌
    }
}

얻어가는 것

• 지금까지 dp는 Top-Down만 고집했었는데 Bottom Up이 비교가 안될정도로 쉽다.
• 그리고 직관적이야 너무 좋은걸? 앞으로 dp면 Bottom-up으로 풀어보기 고고고고

느낀점

"220329"

소요 시간 : 2h