문제 설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항
- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
코드
class Solution {
public int solution(int[][] triangle) {
int answer = Integer.MIN_VALUE;
int[] arr = {};
int[] tmp = {};
arr = new int[1];
arr[0] = triangle[0][0];
// [0]번째 행은 연산할 것이 없으므로, [1]번째 행부터 반복문 실행
for(int i=1; i<triangle.length; i++) {
// 연산을 위한 배열 i*2개
tmp = new int[i*2];
int idx = 0;
for(int j=0; j<arr.length; j++) {
tmp[idx++] = arr[j] + triangle[i][j];
tmp[idx++] = arr[j]+ triangle[i][j+1];
}
// 해당 열의 원본 데이터는 i+1개 이므로,
// 중간 원소들은 대소비교를 통해 더 큰 값을 추린 후 i+1개 값만 저장한다.
arr = new int[i+1];
arr[0] = tmp[0];
arr[i] = tmp[i*2-1];
idx = 1;
for(int j=1; j<tmp.length-2; j+=2) {
arr[idx++] = Math.max(tmp[j], tmp[j+1]);
}
}
// 마지막 연산 결과 값중 MAX 값 찾기
for(int i=0; i<arr.length; i++) {
if(answer < arr[i]) answer = arr[i];
}
return answer;
}
}
URL: https://school.programmers.co.kr/learn/courses/30/lessons/43105
'알고리즘' 카테고리의 다른 글
프로그래머스 폰켓몬 (0) | 2022.08.14 |
---|---|
프로그래머스 [1차] 추석 트래픽 (오답) (0) | 2022.08.04 |
프로그래머스 기능개발 (0) | 2022.07.27 |
프로그래머스 신규 아이디 추천 (0) | 2022.07.27 |
프로그래머스 로또의 최고 순위와 최저 순위 (0) | 2022.07.24 |