정수 삼각형

문제: https://school.programmers.co.kr/learn/courses/30/lessons/43105

문제설명

• 주어진 파라미터: int[][] triangle
• 반환값: 거쳐간 숫자의 최댓값 return
• 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중 거쳐간 숫자의 합이 가장 큰 경우를 찾고자 함
• 아래칸 이동시 한칸만 이동 가능

풀이방식

1. 일단 끝까지 가보고 결과값들을 저장해놔야한다.
2. 삼각형의 높이는 1이상 500이하 → 2^499로 완전 탐색은 불가능
3. 각 레벨별 가장 큰 아이끼리 더하면 좋겠지만 연결이 안돼있다면 불가능
4. 아래에서부터 3개 기준 큰 값들을 더한 값으로 교체한다면 최종적으로 남은 값은 최고의 합이 될 것
5. 가장 마지막 열 왼쪽 노드를 기준으로 생각
6. t[n-1][0], t[n-1][1] 각각 t[n-2][0]과 합을 구해 더 큰 값을 t[n-2][0]에 대입
7. 점화식으로 생각 → 2가지 변수 필요(계층, 기준)
   • t[n-1][g], t[n-1][g+1] 각각 t[n-2][g]과 합을 구해 더 큰 값을 t[n-2][g]에 대입

코드

class Solution {
    
    static int[][] t;

    public int solution(int[][] triangle) {

        t = triangle;

        for(int i = triangle.length - 1 ; i > 0; i--){
            for(int j = 0; j < triangle[i].length-1; j++){
                calc(i,j);
            }
        }

        return triangle[0][0];
    }

    public void calc(int n, int k){
        int num1 = t[n][k] + t[n-1][k];
        int num2 = t[n][k+1] + t[n-1][k];

        if(num1 >= num2 ){
            t[n-1][k] = num1;
        }else{
            t[n-1][k] = num2;
        }
    }
}

회고

완전 탐색 중에서도 효율적인 방법만 탐색하는 DP를 공부해보았다! 뿌듯했다!

---

참 쉽쥬잉~?~?