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

문제 설명

programmers.co.kr/learn/courses/30/lessons/43105?language=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

 

풀이

- 모든 경우의 수를 구해보면 되지 않을까? 하고 dfs로 접근했었는데

- 동적계획법으로 점화식을 세워서 풀면 더 간단한 문제였다

- 위에서부터 차례대로 내려오면서, 해당 요소까지의 최댓값을 구하는 식으로 푼다

 

1. answer[y][x] 는 해당 요소까지의 최댓값을 의미한다고 정의
2. 각 행의 가장 왼쪽 요소(x==0)는 바로 위의 요소에서만 이동 가능하므로 위의 요소까지의 최댓값과 더해준다.
   
   • answer[y][x] = answer[y-1][x] + triangle[y][x];
   • ex) 4번째 행의 2의 경우 바로 위 8에서 밖에 이동이 안되기 때문에 8까지의 최댓값을 더해준다는 의미
3. 각 행의 가장 오른쪽 요소(x==y)도 바로 위의 요소에서만 이동 가능하므로 위의 요소까지의 최댓값과 더해준다.
   • answer[y][x] = answer[y-1][x-1] + triangle[y][x]; 
   • ex) 4번째 행의 4의 경우 바로 위 0에서 밖에 이동이 안되기 때문에 0까지의 최댓값을 더해준다는 의미
4. 가운데 요소들은 해당 요소로 이동 가능한 요소 중 최대값을 가진 것과 더해준다.
   • answer[y][x] = Math.max(answer[y-1][x] + triangle[y][x], answer[y-1][x-1] + triangle[y][x]);
   • ex) 4번째 행의 7의 경우  8,1 둘 중의 하나에서 이동되기 때문에 둘 중 경로상 최대합을 가진 것과 더해준다는 의미
5. 마지막 행의 합들 중 최댓값을 구해 리턴한다.

 

코드

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int n = triangle.length;
        int[][] answer = new int[n][n];
        
        answer[0][0] = triangle[0][0];
        
        for(int y=1; y<n; y++)
        {
            for(int x=0; x<=y; x++)
            {
                int value = triangle[y][x];
                if(x == 0){
                    answer[y][x] = answer[y-1][x] + value;
                }
                else if(x == y){
                    answer[y][x] = answer[y-1][x-1] + value;
                }
                else{
                    answer[y][x] = Math.max(answer[y-1][x] + value, answer[y-1][x-1] + value);
                }
            }
        }
        
         return Arrays.stream(answer[n-1]).max().getAsInt();
    }
}

 

셀프 피드백

- 점화식 좀 스스로 세워보자