JAVA 프로그래머스 Lv.3 정수 삼각형

 

https://school.programmers.co.kr/learn/courses/30/lessons/43105

 

---

문제

1. 입력으로 2차원 int 배열 triangle ( 1 <= triangle <= 500, 0 <= triangle[i][j] <= 9999 )이 입력으로 들어옴.
2. 삼각형의 꼭대기에서 바닥까지 연결되는 경로 중 거쳐간 숫자의 합이 가장 큰 경우를 출력.
3. 아래 칸으로 이동할 때 대각선방향으로 오른쪽 왼쪽 중 한 쪽으로만 이동이 가능하다.

---

 

최종 코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                if (j == 0) {
                    triangle[i][j] = triangle[i - 1][j] + triangle[i][j];
                } else if (j == i) {
                    triangle[i][j] = triangle[i - 1][j - 1] + triangle[i][j];
                } else {
                    triangle[i][j] = Math.max(triangle[i - 1][j - 1] + triangle[i][j],
                            triangle[i - 1][j] + triangle[i][j]);
                }
                if (i == triangle.length - 1) {
                    answer = Math.max(answer, triangle[i][j]);
                }
            }
        }
        
        return answer;
    }
}

 

어떻게 시간 초과가 나지 않고 최대한 간결하게 답을 구할 수 있을 것인지 생각해보는 것이 가장 중요한 것 같다.

 

내가 코드를 짤 때 가장 핵심적인 포인트는 누적합 방식으로 해당 위치에 올 수 있는 가장 큰 값을 넣는 것이었다.

 

 

먼저 해당 배열에 들어갈 가장 큰 값을 구하는 것에는 세 개의 조건문이 쓰였다.

 

1. 해당 위치가 0번 열일 때는 상위 행의 0번 열 값과 해당 위치에 있는 값을 더한다.

if (j == 0) {
    triangle[i][j] = triangle[i - 1][j] + triangle[i][j];
}

 

2. 해당 위치가 행의 마지막 열일 때에는 상위 행의 마지막 열 값과 해당 위치의 값을 더한다.

 else if (j == i) {
    triangle[i][j] = triangle[i - 1][j - 1] + triangle[i][j];
}

 

3. 처음이나 마지막 열이 아니고 사이에 있는 열일 경우에는 상위 행의 [해당 열 번호 - 1] 번과 [해당 열 번호]의 값과 해당 위치의 값을 더해 두 개의 결과를 두고 더 큰 값을 선택할 수 있도록 한다.

else {
    triangle[i][j] = Math.max(triangle[i - 1][j - 1] + triangle[i][j],
            triangle[i - 1][j] + triangle[i][j]);
}

 

 

최종 값을 구하기 위해서 쓰인 조건은

if (i == triangle.length - 1) {
    answer = Math.max(answer, triangle[i][j]);
}

 

해당 행이 마지막 행일 때 행의 모든 값을 비교하여 가장 큰 값을 출력하는 것이다.

 

어떻게 문제를 풀 것인지 계산만 하면 쉬운 것 같은데 그 과정이 조금 걸리는 것 같다.