7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력 | 출력 |
---|---|
5 | |
7 | |
3 8 | |
8 1 0 | |
2 7 4 4 | |
4 5 2 6 5 | 30 |
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
dp!!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static List<int[]> dp;
private static List<Integer>[] triangle;
private static int height;
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
height = Integer.parseInt(reader.readLine());
triangle = new List[height];
dp = new ArrayList<>();
for (int i = 0; i < height; i++) {
triangle[i] = new ArrayList<>();
StringTokenizer angleToken = new StringTokenizer(reader.readLine());
dp.add(new int[i + 1]);
for (int j = 0; j < i + 1; j++) {
triangle[i].add(Integer.parseInt(angleToken.nextToken()));
}
}
dp.get(0)[0] = triangle[0].get(0);
for (int i = 0; i < height - 1; i++) {
for (int j = 0; j < i + 1 ; j++) {
int pre = dp.get(i)[j];
dp.get(i + 1)[j] = Math.max(dp.get(i + 1)[j], pre + triangle[i + 1].get(j));
dp.get(i + 1)[j + 1] = Math.max(dp.get(i + 1)[j + 1], pre + triangle[i + 1].get(j + 1));
}
}
int result = Integer.MIN_VALUE;
for (int value : dp.get(height - 1)) {
result = Math.max(result, value);
}
System.out.println(result);
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}