[알고리즘]프로그래머스 43105번 - 정수 삼각형

프로그래머스 43105번 - 정수 삼각형

프로그래머스 43105번 - https://programmers.co.kr/learn/courses/30/lessons/43105

 

요구사항

1. 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 최댓값을 반환하라.

2. 단, 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.

 

요구사항 분석 및  풀이과정

1. 주어진 삼각형은 시각적인 표현이고, 삼각형을 배열로 보면 다음과 같습니다.

 

배열로 표현한 삼각형

 

2. 시각적으로 표현된 삼각형 기준으로 아래 칸으로 이동할 때 대각선 방향으로 한 칸 오른쪽 또는 왼쪽이기 때문에, 위 모양을 기준으로는 아래 방향 또는 우측 하단 대각선 방향으로만 이동이 가능합니다.

 

3. 2번을 경유해오는 칸을 도착하는 칸을 시점으로 보면 왼쪽 상단 대각선 방향 또는 위쪽 방향에서 올 수 있습니다. 그림으로 표현해보면 다음과 같습니다.

 

도착하는 칸 시점

 

4. 3번을 고려하여 주어진 규칙대로 계산하면 됩니다. 단, 계산의 편의를 위하여 구역을 3 부분으로 나누어 계산하겠습니다.

 

구역을 나눈 모습

 

빨간색 구역은 위쪽 칸에서만, 파란색 구역은 왼쪽 상단 대각선 칸에서만, 초록색 구역은 왼쪽 상단 대각선 칸 또는 위쪽 칸에서만 올 수 있습니다. 

 

빨간색 구역의 경우는 규칙에 의하여 위쪽 칸의 값만 누적하여 더해주면 됩니다. 파란색 구역 또한 왼쪽 상단 대각선 칸의 값만 누적하여 더해주면 됩니다. 또한 두 구역은 계산에 필요한 칸의 값이 서로 독립적이므로 구역의 계산 순서가 중요하지 않습니다.

 

하지만 초록색 구역의 경우는 계산을 위하여 이미 계산된 빨간색 구역과 파란색 구역의 값이 필요하므로, 가장 나중에 계산을 해주어야 합니다.

 

이때 초록색 구역은 규칙에 의하여 위쪽 칸의 값과 왼쪽 상단 대각선 칸의 값 중 큰 값을 선택하여 누적하여 더해주면 됩니다.

 

각 칸의 값은 양수이므로 아래 방향으로 내려가면서 거쳐간 숫자의 합은 증가하게 되고, 가장 마지막 줄에서 가장 큰 수가 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중 거쳐간 숫자의 최댓값입니다.

 

소스코드 작성

import java.util.Arrays;

class Solution {
    
    public int solution(int[][] triangle) {
        for (int row = 1; row < triangle.length; row++) {
            triangle[row][0] += triangle[row-1][0]; // 빨간 구역
            triangle[row][row] += triangle[row-1][row-1]; // 파란 구역
            
            // 초록 구역
            for (int col = 1; col < row; col++)  {
                triangle[row][col] += Math.max(triangle[row-1][col-1], triangle[row-1][col]);
            }
        }

        return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
    }
}

 

결과

 

소스코드 깃허브 주소

링크