백준 [자바 java] 1932번 : 정수삼각형

import java.io.*;
import java.util.*;



class Main {
	
	
	public static void main(String[] arg) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader (System.in));
		StringTokenizer st;
		
		
		int n = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[n+1][n+1];
		int[][] dp = new int[n+1][n+1];
		
		int i,j;
		for(i = 1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			for(j = 1;j<=i;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				
			}
		}
		
		dp[1][1] = arr[1][1];
		
		int max = arr[1][1];
		
		
		for(i = 2;i<=n;i++) {
			
			for(j = 1;j<=i;j++) {
				if(j == 1) {
					dp[i][j] = dp[i-1][j]+arr[i][j];
				}
				else if(j == i) {
					 dp[i][j] = dp[i-1][j-1]+arr[i][j];
				}
				else {
			   dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1])+arr[i][j];
				}
				max = Math.max(dp[i][j],max);
			}
		}
		
	System.out.println(max);
		
}

}

 본의 아니게 dp문제만 왕창 풀게 되네요ㅜㅜ 아마 제가 풀 문제를 고를 때 맞은 사람이 많은 순서대로 골라서인 것 같아요! dp문제가 인기가 많나 봅니다ㅋㅋ

이 문제는 정수 삼각형의 꼭대기에서 1층으로 내려올 때 가장 큰 값을 구하는 문제입니다.

실버1 난이도의 문제 치고는 쉬운 문제였어요! 먼저 arr에 수를 입력받고 dp를 채워 넣는 형식입니다. 해당 dp는 2차원 배열 기준으로 바로 위 그리고 바로 위의 왼쪽 중 큰 것을 해당 arr에 더해 저장하고 저장 가능한 dp가 하나뿐이면 그냥 그것에 해당 arr을 더해 저장하도록 하였습니다. 그리고 max를 구해서 출력하면 완성입니다. 

 

실수 1. max값을 0으로 설정했어요 그러면 n이 1일 때 arr [1][1] 값이 아닌 0이 출력됩니다.

 

알아야 할 것: n값에 1을 넣어도 값이 같을 것이라고 상상하지 말고 직접 출력시켜보기

 

다른 사람의 코드와 다른 점 : 딱히 없따