알고리즘 문제 풀이를 블로그에 올리는 이유는 풀이, 코드를 기록하기 위함이니
앞으로 문제를 다 긁어오기보다 링크만 두고 풀이가 잘 보이도록 포스팅 할 예정입니다!

📄 문제

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

---

👩‍💻 풀이

1. 문제 이해

이 문제는 위 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아 최대 숫자 합을 반환하는 문제이다.

2. top-down 풀이

• 동적계획법을 활용하여 숫자 합을 담을 2차원 배열 dp[triangle.length][triangle.length] 선언
• dp[0][0]에는 삼각형 꼭짓점의 값을 담고,
  왼쪽으로만 내려갔을 때의 값을 dp[i][0]에,
  오른쪽으로만 내려갔을 때의 값을 dp[i][i]에 담음
  
• 2차원 배열 dp에서 왼쪽 합, 오른쪽 합으로 둘러쌓인 부분을 동적 계획법을 활용하여 채워 나감
  dp[2][1]에서부터 시작하여 반복문을 돌면서,
  (연결될 수 있는)윗 줄에 있는 값 중 큰 값에 해당 위치의 삼각형 값을 더함
  예) dp[2][1] : 10과 15 중 큰 15에 해당 위치(삼각형에서 (2,1)) 삼각형 값인 1을 더해 16 입력
  예) dp[3][1] : 연결될 수 있는 값인 18과 16 중 큰 18에 해당 위치(삼각형에서 (3,1)) 삼각형 값인 7을 더해 25 입력
  
• 동적 계획법을 활용하는 반복문이 끝나면 dp 행렬 맨 마지막 줄을 돌면서 max 값 탐색 및 갱신
• 최종적으로 구해진 max 값 반환

public class Solution {

    public static void main(String[] args) {
        int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};

        System.out.println("top-down 풀이 : " + solution1(triangle));
    }

    //top-down
    public static int solution1(int[][] triangle) {
        // 1. 기본값 초기화  //
        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] = dp[i - 1][0] + triangle[i][0];
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
        }

        // 2. 동적계획법 //
        for(int i = 2; i < triangle.length; i++) {
            for(int j = 1; j < i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
            }
        }

        // 3. 최대값 반환 //
        int max = 0;
        for(int i = 0; i < dp.length; i++) {
            max = Math.max(max, dp[dp.length - 1][i]);
        }

        return max;
    }
}

3. bottom-up 풀이

• 동적 계획법을 활용하되, 삼각형 맨 아래에서부터 큰 값을 선택하여 더해나가며 triangle 값을 갱신 해주는 방식
• 마지막에 최종적으로 갱신된 최댓값 = 삼각형 꼭대기 값(triangle[0][0])을 반환

public class Solution {

    public static void main(String[] args) {
        int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};

        System.out.println("bottom-up 풀이 : " + solution2(triangle));
    }

    //bottom-up
    public static int solution2(int[][] triangle) {
        for(int i = triangle.length-2; i >= 0; i--) {
            for(int j = 0; j < triangle[i].length; j++) {
                triangle[i][j] += Math.max(triangle[i+1][j],triangle[i+1][j+1]);
            }
        }

        return triangle[0][0];
    }
}