[프로그래머스] 3️⃣ 정수 삼각형(JAVA)

🔗 문제 링크 

 

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

 

---

⛈️  문제 설명 

 

 

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

 

 

 

---

 

⛈️  풀이 과정

 

① 현재 위치에서 최대 합을 구할 때, 이전 레벨에서부터 올 수 있는 두 경로 중 더 큰 값을 선택

② 이를 위해 dp 배열을 사용하여 각 위치까지 올 수 있는 최대 합을 저장 

③ 맨 위에서부터 시작하여 차례대로 삼각형의 아래로 내려가면서 값을 갱신

④ 마지막 줄까지 계산이 끝나면, 마지막 줄에서 가장 큰 값이 바로 정답

 

 

 

 

---

⛈️  풀이 코드

 

import java.util.*;

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

        // 첫 번째 숫자는 바로 초기화
        dp[0][0] = triangle[0][0];

        // DP 테이블 채우기
        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];

            // 중간의 값들 (위에서 두 경로 중 더 큰 값 선택)
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }

        // 마지막 행에서 가장 큰 값을 찾아서 반환
        for (int i = 0; i < triangle[triangle.length - 1].length; i++) {
            answer = Math.max(dp[triangle.length - 1][i], answer);
        }

        return answer;
    }
}

 

 

⛈️  공간 최적화 코드 😇

public int solution(int[][] triangle) {
    // 두 번째 줄부터 삼각형을 업데이트
    for (int i = 1; i < triangle.length; i++) {
        // 왼쪽 가장자리 값 (오직 위에서만 값이 내려옴)
        triangle[i][0] += triangle[i-1][0];
        
        // 오른쪽 가장자리 값 (오직 왼쪽 대각선 위에서만 값이 내려옴)
        triangle[i][i] += triangle[i-1][i-1];
        
        // 중간 값들 (위의 두 경로 중 더 큰 값을 선택해서 더함)
        for (int j = 1; j < i; j++) {
            triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
        }
    }

    // 마지막 줄에서 가장 큰 값 반환
    return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
}

 

 

---

 

 

☀️  한번 더 생각해 보자! 

📍dp ,  이전 값들을 어떻게 사용할지