[프로그래머스]정수 삼각형

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

두 번째로 푼 날(2022_03_09)

나이브하게 푼다고 생각하면, 2 x 2^2 x 2^3 x ... 의 경우의 수가 되기 때문에 엄청나게 많은 경우의수가 나오게 된다.
i 번째 level에서 j번째 원소에서 매 번 두 가지 경로로 이동 가능하다.
[i-1][j] 와 [i-1][j+1] 모두 [i][j+1]로 이동이 가능하다.
즉 반복해서 solve 해야하는 problem이 등장한다는 것이다 -> dp

dp[i][j] 를 i번째 level j번째 원소에서 바닥까지 가는 경로의최대 합이라고 한다면
dp[i][j] = triangle[i][j] + Math.max(dynamic(i+1,j),dynamic(i+1,j+1)) 의 점화식이 나온다.
(20분)

import java.util.*;

class Solution {
    public int depth = 0; // 전체 depth
    public int[][] gt; // triangle 인풋 
    public int[][] dp = new int[500][500];
    // 10000 x 500 -> 500만 int형으로 가능. dp 배열의 타입을 int형으로 해도 괜찮다.
    public int solution(int[][] triangle) {
        int answer = 0;
        gt = triangle;
        depth = triangle.length-1;
        // 삼각형 이루는 모든 숫자는 0이사이기 때문에 dp 는 -1로 초기화 해도 된다. 
        for(int i =0 ; i<=depth;i++) Arrays.fill(dp[i],-1);
        // dynamic 호출 
        answer = dynamic(0,0);
        return answer;
    }
    public int dynamic(int i, int j){
        if ( i == depth) return gt[i][j];
        if ( dp[i][j] != -1 ) return dp[i][j];
        return dp[i][j] = gt[i][j] + Math.max(dynamic(i+1,j),dynamic(i+1,j+1));
    }
}

문제 풀이

(30:)

꼭대기 → 바닥 까지의 경로 중, “거쳐간 숫자의 합”이 “가장 큰 경우”를 찾아보려 한다.

아래칸으로 이동 시, 대각선 방향 “한 칸 오른쪽 or 한칸 왼쪽”으로만 이동이 가능 ( 한 칸!)

이 문제는 동적 계획법으로 풀어야 할 것 같다.

왜냐하면, 오른쪽 or 왼쪽의 두 가지 종류의 이동이 있을 때, 현재 더 큰 쪽으로 이동한다고 최대값이 나온다는 보장이 없기 때문이다. 즉, 두 가지 방향 모두를 해 봐야하는데, 이 때 겹치는 경우는 다음과 같다

  7
3
  1
과
 7
   8
 1

여기서 1로 오는 경로는 결국 한 층 위의 왼쪽, 오른쪽 노드로부터 오는 것이다. → 1은 이 중 최댓값 하나만을 갖고 있으면 된다.

이 문제의 경우, 이런식으로 1을 위에서 내려오는 두 경우에 대해서만 즉각적으로 업데이트 시켜주면 결국 ( 500 + 499 + .. 2) x 2 정도의 연산만이 나올 것 같다 ->124750 으로 감당가능

• 이를 위해서는 같은 depth의 노드들을 모두 업데이트 하고 나서 다음 depth를 처리해야할 것 같다
• dp는 2차원 배열로 [depth][width] 로 한다
  즉,
  7
  1 3 8
  에서 8은 [1][2] 의 위치인 것이다.

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int depth = triangle.length;
        int low = depth - 1;
        int dp[][] = new int[depth][triangle[depth-1].length]; 
        
        dp[0][0] = triangle[0][0];
        // print(triangle);
        for(int d = 0 ; d < depth-1 ;d++){
            for(int w = 0 ; w <= d ; w++){
                // triangle[d+1][w] + triangle[d][w] , triangle[d+1][w+1] + triangle[d][w] , dp[]
                dp[d+1][w] = Math.max(triangle[d+1][w] + dp[d][w],dp[d+1][w]);
                dp[d+1][w+1] = Math.max(triangle[d+1][w+1] + dp[d][w], dp[d+1][w+1]);
            }
        }
        // print(dp);
        for(int w = 0; w < dp[low].length; w++){
            answer = Math.max(dp[low][w],answer);
        }
        
        return answer;
    }
}

잠시 있고 있던 JAVA의 배열

주어진 triangle은
triangle[0].length = 1
triangle[1].length = 3
triangle[2].length = 5