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

문제 링크

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

코딩테스트 연습 - 정수 삼각형

 

이 문제의 경우 효율성 검사가 들어가있다.

그 의미는 무엇이냐? 완전탐색이나 다중 for문과 같은 방식은 out이라는 뜻!

 

필자의 경우 다이나믹 프로그래밍(Dynamic Programming) 기법을 사용하였다.

 

다이나믹 프로그래밍이란?

 

다이나믹 프로그래밍이란 복잡한 문제를 간단한 여러개의 문제로 나눠 푸는 것을 의미한다.

한마디로 하나의 큰 문제를 여러개의 작은 단위로 쪼갠다는 뜻이다.

 

분할 정복 알고리즘(Divide and conquer)과는 개념이 비슷해 보이지만

다이나믹 프로그래밍은 나눠진 문제들이 '중복'되어 재사용된다는 점에서 차이점을 둔다.

 

가장 최소단위 값부터 구하고, 규칙에 따라 그 값에 차곡차곡 값을 더해서 결과값을 반환한다고 생각하면 좀 쉽다.(이전 문제에 대한 답에 현재 문제의 답을 더하기 때문에 문제가 '재사용'된다.)

 

 

풀이 방식

 

필자의 경우, 재귀를 통해 해당 문제를 풀었다.가장 맨 밑 층의 값들까지 도달한 뒤, 바닥의 인접한 두 값 중 더 큰 값을 바로 위 층의 값에 합산하는 방식이다.즉, 바닥부터 시작해서 위로 거꾸로 올라가는 방식으로 값을 구할 것이다.그림을 통해 좀 더 쉽게 다가가보자.

 

 

재귀를 통해 가장 맨 밑층에 도달했을 때,

4와 5 중 더 큰 숫자를 찾는다.

해당 값을 4와 5 바로 위에 있는 2에 더해준다.

 

왜? 이 문제는 최상층부터 아래로 숫자를 타고 내려가는 방식이다.

4와 5로 접근하기 위해서는 2를 무조건 지나가야 하기 때문

(4와 5로 접근하기 바로 전 단계가 2)

 

 

 

 

 

그 다음, 5와 2 중 더 큰 값인 5를 바로 위의 값 7에 합산한다.

이러한 방식으로 맨 밑층 숫자를 비교하여 더 큰 값을

바로 윗층에 합산한다.

 

 

 

 

 

 

2층도 마찬가지로 합산한 값들을 대소 비교하여 3층 값에 합산해준다.

옆 그림의 경우 12가 더 크므로 숫자 8에 12를 더해줄 것이다.

이러한 방식으로 꼭대기 층까지 진행하면 거처간 숫자의 최댓값을 구할 수 있다.

 

 

 

 

 

 

 

 

 

그림과 같이 최댓값 30을 구할 수 있다.

 

 

 

 

 

 

꼭대기에서 바닥까지 합산한 최댓값의 경로는 이러하다.

 

이제 왜 다이나믹 프로그래밍인지 알겠는가?

층을 올라갈수록 자기 자신의 값에 아랫층 최대값을 계속해서 합산해나가는 방식이기 때문이다.

 

 

 

 

코드 풀이

 

class Solution {
    int [][] dp;
    
    public int findMax(int index, int[][] triangle, int depth) {
        if (depth == triangle.length) 
            return dp[depth][index];
        if (dp[depth][index] == 0)
            dp[depth][index] = Math.max(findMax(index, triangle, depth + 1), //왼쪽 오른쪽 중 큰값 반환
                            findMax(index + 1, triangle, depth + 1)) + triangle[depth][index];
        return dp[depth][index];
    }
    public int solution(int[][] triangle) {
        dp = new int[triangle.length][triangle.length];
        //dp 맨 밑을 triangle과 똑같이 세팅
        for (int i = 0; i < triangle.length; i++)
            dp[triangle.length - 1][i] = triangle[triangle.length - 1][i];
        int max = findMax(0, triangle, 0);
        return max;
    }
}

 

필자와 달리 for문을 이용하여 선형으로 구하는 방식도 있다. 다만 이 방식이 다이나믹 프로그래밍 알고리즘에는 좀 더 적합하다고 판단하여 채택했다. 재귀 코드가 헷갈린다면 재귀의 기초격인 피보나치 수열의 재귀 풀이부터 보고 오는 것을 추천한다.