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

문제 링크

프로그래머스

---

사실 알고리즘 문제를 하루에 한 문제 이상 풀고 있는데, 포스팅을 하지 않았습니다.

왜냐면,, 요새 스프링 공부를 열심히 하다보니... 포스팅을 하지 않는 대신 스프링 공부에 집중해야겠다고 생각했어요! 😅

10월 초 연휴를 아주 재밌게 즐기고 오고 나서, 문득 오늘 푼 알고리즘 문제라도 포스팅해보자! 하고 생각이 들어서 포스팅하게 되었습니다!

풀이

2차원 바텀업 DP로 풀이했습니다.

이 문제는 사실 전에 풀었던 2096번: 내려가기 문제와 유사한 풀이로 가능합니다.

문제의 내용처럼 경로 중 거쳐간 숫자의 합의 최댓값을 찾는 것이 이 문제의 목적이기 때문에,

이전에 거쳐갔던 숫자들의 최댓값 합을 계속해서 메모이제이션해두고 맨 마지막 값을 결과로 내보내면 됩니다.

 

전에 풀었던 문제와의 차이점이라 하면 이 문제는 삼각형으로 진행한다는 점입니다.

진행할 때 어떤 조건이 발생하는가 생각해 보면, 다음 세가지 조건을 생각해낼 수 있습니다.

• 한 줄에 있는 값의 첫번째 값은 이전 줄에 있는 값의  오른쪽 값(\(j\))만 더할 수 있습니다.
• 한 줄에 있는 값의 마지막 값은 이전 줄에 있는 값의  왼쪽 값(\(j - 1\))만 더할 수 있습니다.
• 한 줄에 있는 값의 중간 값은 이전 줄에 있는 값의  왼쪽과 오른쪽 값(\(j, \ j - 1\))을 더할 수 있습니다.

이 세가지 조건을 유의하면서 DP를 진행해주면 되겠습니다. 다음은 DP 점화식입니다.

\[\begin{aligned} if (j  \neq  0) \ dp[i][j] &= max(dp[i][j], dp[i - 1][j - 1] + triangle[i][j]); \\ if (j \neq i) \ dp[i][j] &= max(dp[i][j], dp[i - 1][j] + triangle[i][j]);\end{aligned}\]

풀이코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int n = triangle.length;
        int[][] dp = new int[n + 1][n + 1];
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j != 0) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + triangle[i][j]);
                if (j != i) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + triangle[i][j]);
                answer = Math.max(answer, dp[i][j]);
            }
        }
        
        return answer;
    }
}

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!