[프로그래머스] 정수 삼각형 (JAVA)

문제 출처 - Programmers

문제는 여기

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

---

[풀이]

1. triangle배열을 맨 아래부터 탐색하며 올라간다.

2. 현재 값과 오른쪽의 값을 비교해 더 큰 값을 위에 값과 더해준다.

3. 모든 값을 더해가면 [0][0]은 가장 큰 값이 저장된다.

4. 3. 에서 구해진 값을 출력한다.

[접근]

1. 맨 밑에서부터 탐색해서 올라가면 되겠다고 생각하였다.

[코드]

class Solution {
    public int solution(int[][] triangle) {
        // 맨 아래부터 시작
        for (int i = triangle.length - 1; i > 0; i--) {
			for (int j = 0; j < i; j++)
				// 본인과 그  왼쪽에 값을 비교해서 더 큰값을 선택
				// 그 후 위에 값과 합치기
				triangle[i - 1][j] += Math.max(triangle[i][j], triangle[i][j + 1]);
		}
        
        return triangle[0][0];
    }
}