문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
문제 풀이
해당 문제는 DP 알고리즘으로 풀 수 있는 문제로 앞에서 계산한 값을 뒤에 계산할 때 사용하는 문제이다.
먼저 문제에서 주어진 배열값을 2차원 배열로 만들고 그 배열과 같은 값인 dp 배열을 만들어 준다. dp 배열을 만들어 주면서 0,0 값은 dp에 초기화 시켜둔다. 해당 초기화는 크게 의미는 없지만 나중에 값을 가져와야 하는 경우를 생각해서 입력 해주면 좋다.
왼쪽은 입력값 배열, 오른쪽은 dp 배열이다.
그렇다면 이제 아래로 내려가면서 위에 있는 값중 자신의 위의 값 [ i - 1 ][ j ] [ i - 1 ][ j - 1] 값을 두개를 각각 계산하여 더 큰값을 dp[i][j] 값에 입력을 하면된다. 순서대로 진행하게 되면 아래 사진과 같이 진행된다.
dp 배열 마지막에서 제일 큰 값이 30이기에 30을 반환 해주면 된다.
나의 답안
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
// 입력 받기
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int idx = 0;
while (st.hasMoreTokens()) {
arr[i][idx++] = Integer.parseInt(st.nextToken());
}
}
System.out.println(bfs(arr, n));
}
private static int bfs(int[][] arr, int n) {
int[][] dp = new int[n][n];
dp[0] = arr[0].clone();
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < i + 1; j++) {
int left = arr[i][j] + dp[i - 1][Math.max(0, j - 1)];
int right = arr[i][j] + dp[i - 1][j];
dp[i][j] = Math.max(left, right);
}
}
return Arrays.stream(dp[n - 1]).max().orElse(0);
}
}
