[Lv.3] 프로그래머스 - 정수 삼각형 : Java

프로그래머스

 

 

 

이해하기

처음 풀었던 방법은 다음과 같다.

• triangle의 맨 위부터 아래까지 큰 수들을 더해나간다.
  • triangle의 맨 왼쪽 줄은 쭉 더하기만 하면 된다.
    • e.g. 7-3-8-2-4
  • triangle의 맨 오른쪽 줄도 마찬가지로 쭉 더하기만 하면 된다.
    • e.g. 7-8-0-4-5
  • 나머지 부분은 자신의 왼쪽 위 수와 오른쪽 위 수 중 큰 수를 더해야 한다.

 

e.g. 7 자리가 가능한 큰 수가 되려면 8과 1 중 더 큰 수를 더하면 된다.

 

 

• 계산이 끝난 triangle의 마지막 줄에서 가장 큰 수를 반환한다.

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];
                } else if (j == i) {
                    triangle[i][j] += triangle[i - 1][j - 1];
                } else {
                    triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);
                }
            }
        }

        for (int n : triangle[triangle.length - 1]) {
            answer = Math.max(answer, n);
        }

        return answer;
    }
}

 

순서가 조금 길지만 구현하는데 크게 어려운 점은 없었다.

 

다만 스터디원분께서 더 쉬운 방법이 될 수도 있다고, 새로운 아이디어를 주셔서 다시 풀어보았다.

 

두 번째 방법은 위 아래 순서를 바꾸는 것이다.

아까는 위부터 아래로 계산해나갔다면, 이번에는 아래부터 위로 계산해나가면 된다.

 

 

맨 밑에서부터 가장 큰 수가 될 수 있도록 더해준다.

예를 들어 맨 왼쪽 4, 5 중 더 큰 수인 5를 그 위인 2에 더해준다.

그 옆의 5, 2 중 더 큰 수인 5를 위의 7에 더해준다.

 

이를 반복하다보면 맨 위 꼭대기 수가 가장 큰 수가 되기에

아까처럼 맨 밑 줄의 최대값을 찾아서 반환하는 것이 아닌

꼭대기 값만 반환하면 된다.

 

훨씬 쉬운 풀이!

 

 

 

 

문제풀이

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

        return triangle[0][0];
    }
}