알고리즘 풀이/백준

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

배게 2018. 5. 1. 03:48
728x90

삼각형의 규칙을 찾아

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

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

출력해줍니다.


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);
	}
	
}