• 정수 삼각형

darklight

sublimevimemacs

Java

문제 설명

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

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

제한사항

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

입출력 예

출처

오답

import java.util.*;

class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    
    public int solution(int[][] triangle) {
        dfs(triangle, 0, 0, 0);
        
        return Collections.max(list);
    }
    
    private void dfs(int[][] triangle, int depth, int sum, int idx){
        if(depth > triangle.length - 1){
            list.add(sum);
            return;
        }
        
        if(depth == 0){
            sum += triangle[depth][idx];
            dfs(triangle, depth + 1, sum, idx);    
        }else{
            sum += triangle[depth][idx];
            dfs(triangle, depth + 1, sum, idx);
            sum -= triangle[depth][idx];
            sum += triangle[depth][idx + 1];
            dfs(triangle, depth + 1, sum, idx + 1);   
        }
    }
}

오답 풀이

1. 답은 제대로 나오지만, 완전탐색이기에 DP보다 시간 및 메모리 소비가 매우 크다. 이 점때문에 오답으로 처리되었다.

정답

import java.util.*;

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

        int[][] dp = new int[triangle.length][triangle.length];
        dp[0][0] = triangle[0][0];

        for (int i=1; i< triangle.length; i++) {

            dp[i][0] = triangle[i][0] + dp[i - 1][0];

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

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

        int answer = max;
        return answer;
    }
}

1. 가로, 세로의 길이가 triangle 2차원 배열의 길이와 같은 2차원 배열 dp 생성

   int[][] dp = new int[triangle.length][triangle.length];