190119 DP (3) 정수 삼각형

2019-01-19

DP (3) 정수 삼각형

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 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 int solution(int[][] triangle) {
        int answer = 0;
        int[][] dp=new int[501][501];
        // dp배열: 그 노드에 올때까지 거쳐간 숫자의 최대값
        for(int i=1;i<=triangle.length;i++){
            for(int j=1;j<=i;j++){
                dp[i][j]=triangle[i-1][j-1];
            }
        }
        
        for(int i=2;i<=triangle.length;i++){
            for(int j=1;j<=i;j++){
                // 왼쪽 끝 정수
                if(j==1)
                    dp[i][j]+=dp[i-1][j];
                // 오른쪽 끝 정수
                else if(j==triangle.length)
                    dp[i][j]+=dp[i-1][j-1];
                // 중간에 있는 정수-> 양쪽으로 내려가는 방법이 있으므로 둘중 큰 경로를 선택해서 내려와야 한다.
                else
                    dp[i][j]+=Math.max(dp[i-1][j],dp[i-1][j-1]);
            }
        }
        for(int i=1;i<=triangle.length;i++){
            // 맨 아래에 저장된 거쳐간 숫자들 중 가장 큰 값을 선택
            answer=Math.max(answer,dp[triangle.length][i]);
        }
        return answer;
    }
}
  • 출처 를 참조해서 풀었다!
  • 고민해도 안 풀릴땐 남의 코드를 보는것도 좋은 방법인것 같다…
    • 물론 유사한 유형의 문제를 한번 더 풀어봐야겠지..!