BOJ 1932
위 문제는 백준 사이트의 알고리즘 1932 문제에 관한 설명입니다.
문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때,
이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라.
아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] array = new int[n + 1][n + 1];
int sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
array[i][j] = scanner.nextInt();
if (j == 1) {
array[i][j] = array[i - 1][j] + array[i][j];
} else if (i == j) {
array[i][j] = array[i - 1][j - 1] + array[i][j];
} else {
array[i][j] = Math.max(array[i - 1][j], array[i - 1][j - 1]) + array[i][j];
}
if (array[i][j] > sum)
sum = array[i][j];
}
}
System.out.println(sum);
}
}
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
array[1,1]
array[2,1],[2,2]
array[3,1],[3,2],[3,3]
array[4,1],[4,2],[4,3][4,4]
array[5,1],[5,2],[5,3][5,4][5,5]
위의 순서대로 값들은 들어있습니다.
if (j == 1) {
array[i][j] = array[i - 1][j] + array[i][j];
}
위 부분은 삼각형의 맨 왼쪽 부분을 더하는 부분입니다.
else if (i == j) {
array[i][j] = array[i - 1][j - 1] + array[i][j];
}
위 부분은 삼각형의 맨 오른쪽 부분을 더하는 부분입니다.
else {
array[i][j] = Math.max(array[i - 1][j], array[i - 1][j - 1]) + array[i][j];
}
위 부분은 삼각형의 가운데 부분을 더하는 부분입니다.
가운데는 상단의 좌 우에서 하나씩 올 수 있습니다.
그 중 큰값을 선택해야하기 때문에 Math.max를 이용합니다.
맨 아랫 쪽에는 자동으로 하나씩 더해진 값이 있기 때문에 출력은 맨 아래 중 가장 큰 값
if (array[i][j] > sum)
sum = array[i][j];
를 위와같이 표현했습니다.