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

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

프로그래머스

설명

https://commit.tistory.com/56

[백준] 정수 삼각형(JAVA)

위 문제와 동일하다

사실 프로그래머스에선 풀어본 적이 있다

ㄹㅇ 낑낑대면서 구글링해가면서 풀어봤는데

요즘 dp 폼이 올라서 그런가 술술 풀린다

프로그래머스 특유의 매개변수로 입력만 좀 차이를 주면 됨

풀이

/*
 * 프로그래머스 정수 삼각형
 * 백준의 것과 같다
 * 똑같이 풀어보겠음
 */
class Solution {
    public int solution(int[][] triangle) {
        int trLen = triangle.length;
        // 각 줄의 앞 뒤를 비워주기 위해 2를 더함
        // 0으로 초기화되어 크기 비교가 편해짐
        int[][] dp = new int[trLen][trLen + 2];

        for (int i = 0; i < trLen; i++) {
            for (int j = 1; j < i + 2; j++) {
                dp[i][j] = triangle[i][j - 1];

                // 첫 줄을 제외하고 나머지 줄은 그 전줄의 좌/우 수 중 더 큰수를 더해줌
                if (i != 0) {
                    dp[i][j] += Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
                }
            }
        }
        return Arrays.stream(dp[trLen - 1]).max().getAsInt();
    }
}

백준의 문제와 동일

2칸의 여유공간을 뚫어놓고 비교를 쉽게 해주었다

https://github.com/qTeTp/Algo/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/3/43105.%E2%80%85%EC%A0%95%EC%88%98%E2%80%85%EC%82%BC%EA%B0%81%ED%98%95

Algo/프로그래머스/3/43105. 정수 삼각형 at main · qTeTp/Algo