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

첫 시도

• dp문제중 매우 유명한 정수삼각형 문제이다.
• triangle[0][0]을 기저사례로 두고 바텀업 방식으로 해결했다.
• ex) 7 + 3과 dp[1][0]의 값을 비교해 큰 수로 대체시킨다.
• 간단한 문제지만 구현이 생각보다 오래걸렸다. -> 분발할 것 –

해결

• 내용

import java.util.*;

class Solution {

    public static int solution(int[][] triangle) {
        int answer = 0;
        int[][] dp = new int[triangle.length][triangle[triangle.length-1].length];

        dp[0][0] = triangle[0][0];

        for(int i = 0; i<dp.length-1; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j] + triangle[i + 1][j]);
                dp[i + 1][j + 1] = dp[i][j] + triangle[i + 1][j + 1];
            }
        }
        Arrays.sort(dp[dp.length-1]);
        answer = dp[dp.length-1][dp[0].length-1];

        return answer;
    }
}

참고

• 직접구현