|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public int solution(int[][] triangle) {
int answer = 0;
int row = triangle.length;
for (int i = 1; i < row; i++) {
for (int j = 0; j < triangle[i].length; j++) {
if (j == 0) // 맨 좌측 열
triangle[i][j] += triangle[i - 1][j];
else if (j == triangle[i].length - 1) // 맨 우측 열
triangle[i][j] += triangle[i - 1][j - 1];
else // 중간 열
triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);
}
}
int max = 0;
for (int i = 0; i < triangle[row - 1].length; i++)
max = Math.max(triangle[row - 1][i], max);
// 최대 값 저장
answer = max;
return answer;
}
}
|
cs |
동적 할당법을 이용하여 최대 값을 계산하였다.
Level 2에서 풀었었던 땅따먹기 문제와 비슷해서 쉽게 해결하였다.
https://programmers.co.kr/learn/courses/30/lessons/12913
코딩테스트 연습 - 땅따먹기
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟
programmers.co.kr