[Programmers/Level 3/Java] 정수 삼각형

Programmers(프로그래머스) 정수 삼각형

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

문제 설명

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

풀이

동적계획법(Dynamic Programming)의 가장 기본이 되는 문제이다.
'경로'를 찾는다기 보다는, 거쳐간 숫자의 '누적 합'이 큰 경우를 찾는 문제라고 생각하면 된다.

코드는 다음과 같이 구현하였다.

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        // 각 행을 순회하며 누적 계산
        // 단, 0번째 행은 숫자가 1개뿐이므로 그 다음 행부터 진행
        for(int i = 1; i < triangle.length; i++)
        {
            // 각 행의 원소(열)를 순회하며 누적 계산
            for(int j = 0; j < triangle[i].length; j++)
            {
                // 0번째 원소인 경우, 바로 위에 위치한 숫자를 더함
                if(j == 0)
                    triangle[i][j] += triangle[i-1][j];
                // 행의 마지막 원소인 경우, 왼쪽 위에 위치한 숫자를 더함
                else if(j == triangle[i].length-1)
                    triangle[i][j] += triangle[i-1][j-1];
                // 바로 위에 위치한 숫자와, 왼쪽 위에 위치한 숫자 중에서 큰 수를 더함
                else
                    triangle[i][j] = (triangle[i-1][j-1]+triangle[i][j] > triangle[i-1][j]+triangle[i][j])? triangle[i-1][j-1]+triangle[i][j] : triangle[i-1][j]+triangle[i][j];
            }
        }
        
        // 누적 계산이 끝난 마지막 행에서 가장 큰 수를 answer로 저장
        for(int i = 0; i < triangle[triangle.length-1].length; i++)
            if(answer < triangle[triangle.length-1][i])
                answer = triangle[triangle.length-1][i];
        
        return answer;
    }
}