알고리즘/프로그래머스
[프로그래머스] 정수 삼각형 Java 풀이 및 해설
승민아
2024. 4. 14. 16:08
https://school.programmers.co.kr/learn/courses/30/lessons/43105
풀이 방법
위의 피라미드는 다음과 같은 배열로 들어온다.
7 | ||||
3 | 8 | |||
8 | 1 | 0 | ||
2 | 7 | 4 | 4 | |
4 | 5 | 2 | 6 | 5 |
아래의 층부터 위로 채워나갈 예정이다.
2 7 4 4가 존재하는 층 시작한다.
2 는 다음과 같은 선택지가 있다.
7 | ||||
3 | 8 | |||
8 | 1 | 0 | ||
2 | 7 | 4 | 4 | |
4 | 5 | 2 | 6 | 5 |
4 와 5중에 더 큰 수를 2에 더하면 된다.
이때 2에 5를 더해주면 된다.
다음은 7에 대해 이야기해보자.
7에서 선택할 수 있는 수는 5와 2이다.
7 | ||||
3 | 8 | |||
8 | 1 | 0 | ||
2 | 7 | 4 | 4 | |
4 | 5 | 2 | 6 | 5 |
7 입장에서 5와 2중에서 더 큰 수를 자신에게 더하면 된다.
7에 5를 더해주는 것이다.
이런식으로 위층으로 이동하며 갱신해준다.
최종적으로 맨 꼭대기층에서는 만들 수 있는 최대 수가 들어가있게 된다.
전체 코드
import java.util.*;
class Solution {
public int solution(int[][] triangle) {
int answer = 0;
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]);
}
}
answer = triangle[0][0];
return answer;
}
}