[백준/java] 1932번: 정수 삼각형 - DP

1932번: 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

728x90

 

※ 문제 풀이 도출 과정

 

정수 삼각형 문제풀이

위에서부터 내려오면서 셀에 있는 값을

이전 행의 값을 더한다. 이전행의 값을 더할 때 방향은 ↓↘.

근데 그 중에 더 큰값을 선택해야 한다.

 

반응형

 

정수 삼각형 문제풀이

제일 첫번째 열은 그냥 수직으로 누적 합을 구해주면 된다.

두번째 열부터 현재 행이 i번째 행, 현재 열이 j번째 열이라고 한다면, 

i-1행의 j-1과 i-1행의 j번째의 값과 비교하여 더 큰 수를 누적하여 더해주면 된다.

 

여기서 중요한 것은

삼각형의 크기가 1부터 500까지이기 때문에 

n= 1 일때에도 값이 제대로 나올 수 있도록 처리해줘야 한다.

예를 들어,

1

1

을 입력하면 1이 나와야 한다.

 

위의 경우를 고려하지 않아서 생각보다 많이 틀린 문제이다.

 

package dp;

import java.util.Scanner;
public class IntTriangle {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[][] arr = new long[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		long max = 0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j <= i; j++) {
				long temp = 0;
				if(i > 0) temp = j == 0 ? arr[i-1][j] : Math.max(arr[i-1][j-1], arr[i-1][j]);
				arr[i][j] = temp + arr[i][j];
				if(i == arr.length-1) max = Math.max(max, arr[i][j]);
 			}
		}
		
//		for (int i = 0; i < arr.length; i++) {
//			for (int j = 0; j <= i; j++) {
//				System.out.print(arr[i][j] + " ");
//			}
//			System.out.println();
//		}
		
		System.out.println(max);
	}
}