코딩테스트 고득점 kit / 동적계획법(Dynamic Programming) / 정수 삼각형 / JAVA

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

 

입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

---

나의 풀이

class Solution {
    public static int solution(int[][] triangle) {

        int answer = 0;
        answer = recursion(triangle.length-1, 0, triangle);
        return answer;
    }

    public static int recursion(int i, int j, int[][] triangle) {

        if(i == 0) return triangle[i][j];

        if(triangle[i][j] > triangle[i][j+1]) triangle[i-1][j] += triangle[i][j];
        else triangle[i-1][j] += triangle[i][j+1];

        j+=1;

        if(j > triangle[i].length-2) {
            i -= 1;
            j = 0;
        }

        return recursion(i, j, triangle);
    }
}

---

풀이 분석

생각의 관점을 어떻게 하느냐에 따라서 어려워질 수도 쉬워질 수도 있는 문제인것 같다.

나 같은 경우에는 거꾸로 올라가는 방식으로 생각해서 풀었다.

아래서부터 숫자를 비교해서 더 큰 숫자를 위로 올리는 방식으로 타고타고 올라가다보면 맨위는 자동으로 제일 큰 수가 남아있게 된다. 다음과 같은 원리를 이용해서 재귀로 코드를 풀면 풀이가 생각보다 간단해진다.