[Lv3] 정수 삼각형

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 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

 

문제 원출처: http://stats.ioinformatics.org/countries/SWE

 

 

---

 

이전에 이미 푼 문제와 유사한 케이스입니다.

[Coding Quiz/programmers] - [Lv2] 땅따먹기

 

심지어 한번 뛴 자리로 뛸 수 없다 같은 조건이 명시되어 있질 않으니 문제 자체는 더 쉽게 느껴집니다.

어차피 풀이법은 같지만.

 

 

전 처럼 위에서 아래로 내려보는 것이 아니라,

 

한 칸 아랫 단계에서 위를 바라보는 시점으로 진행할 겁니다.

 

양 사이드는 선택지가 하나(맨 왼쪽은 오른위, 맨 오른쪽은 왼위) 뿐이고, 나머지는 왼위와 오른위 중 큰 수를 자신에게 가져와 더합니다.

 

아래에서 위를 쳐다보는 시점을 유지한 채로 내려옵니다.

 

앞에서 자신에게 가져와 누적한 층이 윗 층이 되어 있을테고, 계속해서 내려오면 됩니다.

 

public int solution(int[][] triangle) {
    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][0];
            } else if(j==triangle[i].length-1) {
                triangle[i][j]+=triangle[i-1][triangle[i-1].length-1];
            } else {
                int big = Math.max(triangle[i-1][j-1], triangle[i-1][j]);
                triangle[i][j]+=big;
            }
        }
    }
    int big = 0;
    for(int i=0;i<triangle[triangle.length-1].length;i++) {
        if(triangle[triangle.length-1][i]>big) big=triangle[triangle.length-1][i];
    }
    return big;
}

마지막까지 내려와서는 마지막 층 애들 중 가장 큰 수를 반환하면 끝.