[programmers] 정수 삼각형 - Python, Java

📖문제

코딩테스트 연습 - 정수 삼각형 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

✨핵심 내용 

- 거쳐간 숫자의 합이 가장 큰 경우 찾기 
- 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 "오른쪽 또는 왼쪽"으로만 이동 가능

 

🤔해결 아이디어 

유형: DP
 
현재 위치(i, j)에서 최댓값이 되려면
왼쪽 위(i-1, j-1) vs 오른쪽 위(i-1, j) 중 어느 방향으로 와야 최댓값이 되는지 찾기

---

✅정답 코드 (Python)

def solution(triangle):
    n = len(triangle)
    m = len(triangle[n - 1])

    # 1. dp 정의 - (i, j) 위치까지의 경로 중 숫자의 합의 최댓값
    dp = [[0 for _ in range(n)] for _ in range(m)]

    # 2. dp 초기화
    # 2-1. dp[0][0] 초기화
    dp[0][0] = triangle[0][0]

    for i in range(1, n):
        # // 2-2. dp[i][0] 초기화
        dp[i][0] = dp[i - 1][0] + triangle[i][0]
        
        # //2-3. dp[i][cnt] 초기화
        dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]

    # 3. 점화식
    for i in range(2, n):
        for j in range(1, i):
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]

    return max(dp[n - 1])

 

✅정답 코드 (Java)

class Solution {
    public int solution(int[][] triangle) {
        int n = triangle.length;
        int m = triangle[n-1].length;

        // 1. dp 정의 - (i, j) 위치까지의 경로 중 숫자의 합의 최댓값
        int[][] dp = new int[n][m];

        // 2. dp 초기화
        // 2-1. dp[0][0] 초기화
        dp[0][0] = triangle[0][0];

        for (int i = 1 ; i < n; i++) {
            // 2-2. dp[i][0] 초기화
            dp[i][0] = dp[i-1][0] + triangle[i][0];

            //2-3. dp[i][cnt] 초기화
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];
        }

        // 3. 점화식
        for (int i = 2; i < n; 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];
            }
        }

        // 4. output
        int mx = 0;
        for (int j = 0; j < m; j++)
            mx = Math.max(mx, dp[n-1][j]);
        return mx;
    }
}