🎯3주차A "정수 삼각형"

🎃문제설명

📐위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

🔒제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

💾입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

🌟문제 이해 및 풀이계획

✏️처음에는 dfs, bfs 처럼 모든 경우의 수를 돌면서 모든 경우의 합을 구하려고 했다. 그래서 큐를 만들어 모든 길을 돌았지만 역시 답도 틀리고 효율성도 꽝이었다.
✏️가는 길은 항상 정해져 있고, 각 길의 최대값은 항상 그대로이기 때문에 이차원 배열을 하나 만들어서 저장해두면 매번 길을 새로 더하지 않아도 된다.

✍🏻내 코드1 - 오답코드 (정답률 32.1%)

import java.util.*;

class Solution {

    public class Status{
        int idx, depth, sum;

        public Status(int idx, int depth, int sum){
            this.idx = idx;
            this.depth = depth;
            this.sum = sum;
        }
    }

    public int solution(int[][] triangle) {
        int answer = 0;
        Queue<Status> q = new LinkedList<Status>();

        int cur_idx = 0;
        int cur_depth = 0;
        int cur_sum = 0;
        q.offer(new Status(0, 0, triangle[0][0])); // 출발점

        while(!q.isEmpty()) {
            Status status = (Status) q.poll();
            cur_idx = status.idx;
            cur_depth = status.depth;
            cur_sum = status.sum;
//          System.out.println(cur_sum);


            if(cur_depth+1 < triangle.length && cur_idx+1 < triangle[cur_depth+1].length) {
                q.offer(new Status(cur_idx, cur_depth+1, cur_sum+triangle[cur_depth+1][cur_idx]));
                q.offer(new Status(cur_idx+1, cur_depth+1, cur_sum+triangle[cur_depth+1][cur_idx+1]));
            }

            if(cur_depth == triangle.length - 1) {
                if(answer < cur_sum) answer = cur_sum;
            }
        }
        return answer;
    }
}

✍🏻내 코드2 - 정답코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int[][] dp = new int[triangle.length][triangle.length];

        dp[0][0] = triangle[0][0];
        for(int i=1; i<triangle.length; i++) {
            dp[i][0] = triangle[i][0] + dp[i-1][0]; // (i, 0)은 무조건 0번째로만 더해진다.
            for(int j=1; j<=i; j++) {
                dp[i][j] = triangle[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);
            }
        }

        for(int i=0; i<dp[triangle.length-1].length; i++) {
            if(answer < dp[triangle.length-1][i]) answer = dp[triangle.length-1][i];
        }

        return answer;
    }
}

✏️(i, 0)은 무조건 0번째만 더해지는 성질을 이용하여 따로 if, else로 나누지 않고 풀이했다.
✏️마지막에 answer를 구하기 위해서 마지막 줄을 for문으로 한번 더 돌았는데, 강사님 풀이방법처럼 Math.max로 계속 비교하면서 갱신해 나간다면 코드를 줄일 수 있을 것 같다.

🍭강의내용

✔️다이나믹 프로그래밍(Dynamic Programming) : 큰 문제를 작은 문제로 나누어 푸는 방법(중간에 계산된 값을 저장해 두었다가 재사용하는 방법)
✔️각각의 삼각형으로 쪼개서 그 안에서의 최대값을 선택하면 된다.

✍🏻강의 코드1 - 위에서 아래로

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0; // 최대값
        
        for(int i=1; i<triangle.length; i++) {
            for(int j=0; j<triangle[i].length; j++) {
                if(j == 0) { // right값만 있는 경우
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j];
                }else if(i == j) { // left만 있는 경우
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j-1];
                }else {
                    int left = triangle[i][j] + triangle[i-1][j-1];
                    int right = triangle[i][j] + triangle[i-1][j];
                    triangle[i][j] = Math.max(left, right);
                }
                
                answer = Math.max(answer, triangle[i][j]);
            }
        }
        return answer;
    }
}

✍🏻강의 코드2 - 아래에서 위로

class Solution {
    public int solution(int[][] triangle) {
        for(int i=triangle.length-2; i>=0; i--) {
            for(int j=0; j<triangle[i].length; j++) {
                int left = triangle[i][j] + triangle[i+1][j];
                int right = triangle[i][j] + triangle[i+1][j+1];
                triangle[i][j] = Math.max(left, right);
            }
        }
        return triangle[0][0]; // 꼭대기 값
    }
}

✔️아래에서 위로 푸는 방법은 배치에 대한 고려를 안해도 되기 때문에 풀이가 훨씬 간결해진다.
=> left, right가 없는 경우에 대한 고려를 하지 않아도 됨! 항상 있기 때문에.

💡아래에서 위로 푸는 방법은 전혀 생각해보지도 않아서 초큼 머리가 띵했다. (사실 좀만 생각해보면 어렵지 않은 방법인데 이래서 강의를 들어야 하나보다.)