[백준][Java] 1932번 숫자삼각형

삼각형의 규칙을 찾아

해당 좌표에 도달하는 가장 큰 값을 배열에 넣어주어

마지막까지 도달하는데 필요한 가장 큰 거리를

출력해줍니다.

n번째 줄의 양사이드로 가는 경로는 단 1개이므로 그냥 넣어주면되고,

양 끝의 사이에 있는 경로는 2가지가 되므로 그 둘 중 더 큰 값을

넣어주면 됩니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int[] res = new int[T]; int max=0; int[][] d= new int[T+1][T+1]; for(int i=1; i<=T; i++) { for(int j=1; j<=i; j++) { d[i][j]=sc.nextInt(); if(j==1) d[i][j] = d[i-1][j] + d[i][j]; else if (j==i) d[i][j] = d[i-1][j-1] + d[i][j]; else d[i][j] = Math.max(d[i-1][j-1], d[i-1][j]) + d[i][j]; if(max<d[i][j]) max=d[i][j]; } } System.out.println(max); } }