문제 링크
https://www.acmicpc.net/problem/1932
문제 풀이
코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int [][] map = new int[n][n];
int [][] dp = new int [n][n];
for(int i=0; i<n; i++){
for(int j=0; j<=i; j++){
map[i][j] = sc.nextInt();
}
}
dp[0][0] = map[0][0];
for(int i=1; i<n; i++){
for(int j=0; j<=i; j++){
if(j==0){
dp[i][j] = map[i][j]+dp[i-1][0];
}else if(j==i){
dp[i][j] = map[i][j] + dp[i-1][i-1];
}else{
dp[i][j] = Math.max(map[i][j]+dp[i-1][j-1], map[i][j]+dp[i-1][j]);
}
}
}
Arrays.sort(dp[n-1]);
System.out.println(dp[n-1][n-1]);
}
}