난이도 : Level 3
- 꼭대기에서 바닥까지 이어지는 경로 중, 가장 경로의 합이 큰 숫자를 리턴하라
- 대각선 경로만 사용하여 아래로 내려갈 수 있다
- 높이: 1 이상 500 이하
- 정수: 0 이상 9,999 이하
해설
- 꼭대기에서 바닥까지 모든 경로의 합 중, 가장 큰 경로의 합을 리턴해야 한다
- 이전까지의 합이 크더라도 현재 방문하는 정수가 크다면 가장 큰 경로가 될 수 있기 때문
- 그러나 모든 경로의 합에서 가장 큰 경로를 매번 구하는 것은 비효율적이므로 동적 계획법을 사용한다
- 2차원 정수형 배열을 선언하고 꼭대기에서 (r, c)까지의 최대 경로의 합을 저장한다
- 경로를 하나씩 늘려가면서 이전에 방문한 점의 가장 큰 누적합을 더하면서 만들어간다
- 모든 삼각형을 방문하여 dp 배열을 완성한다
- 꼭대기에서 바닥까지 온 경로의 누적합 중, 가장 큰 누적합을 리턴한다
public int solution(int[][] triangle) {
int r = triangle.length, c = triangle.length;
int[][] dp = new int[r][c]; // (r,c) 까지 가는데 최대비용
dp[0][0] = triangle[0][0];
for (int i = 1; i < r; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
dp[i][j] = dp[i-1][j] + triangle[i][j];
} else if(j == i) {
dp[i][j] = dp[i-1][j-1] + triangle[i][j];
} else {
dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
}
}
}
return Arrays.stream(dp[r-1]).max().getAsInt();
}
'Algorithm > (Java) PS' 카테고리의 다른 글
[Programmers] 등굣길 (0) | 2023.09.23 |
---|---|
[Programmers] 사칙연산 (0) | 2023.09.23 |
[Programmers] N으로 표현 (0) | 2023.09.22 |
[Programmers][Kakao] 캠핑 (0) | 2023.09.21 |
[Leetcode Top Interview 150] 128. Longest Consecutive Sequence (2) | 2023.09.17 |