백준 1932번 : 정수 삼각형

 문제

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

1932 정수 삼각형

 

 구현 방법

 dp로 구현하였습니다. 각 삼각형 레벨에서 제일 왼쪽, 제일 오른쪽은 더해올 값이 하나이지만 중간의 값들은 왼쪽 위, 오른쪽 위 두 가지를 선택할 수 있으므로 두 가지 값 중 더 큰 값을 저장해줍니다.

dp를 2차원 배열로 선언하여 왼쪽부터 인덱스를 주었을 때 같은 위치에 있는 윗 레벨 값을 현재 위치와 더하여 dp에 저장해줍니다.

만약 중간에 있는 값이라면 다음 인덱스의 값과 현재 위치와 더한 값, dp에 있는 값을 비교하여 더 큰 값을 저장해줍니다.

 

 구현 코드

package BOJ.Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1932_정수삼각형 {
	static int[][] dp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] tri = new int[N][];
		dp = new int[N][];
		for (int i=0;i<N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			tri[i] = new int[i+1];
			dp[i] = new int[i+1];
			for (int j=0;j<tri[i].length;j++) {
				tri[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dp[0][0] = tri[0][0];
		int MAX = Integer.MIN_VALUE;
		for (int i=1;i<N;i++) {
			int cnt = 0;
			for (int j=0;j<tri[i].length;j++) {
				dp[i][j] = dp[i-1][cnt]+tri[i][j]; // dp 값 + 현재 위치 값
				if (j>0 && j<tri[i].length-1) { // 받아 올 값이 2개인 경우
					dp[i][j] = Math.max(dp[i][j], dp[i-1][++cnt]+tri[i][j]);
				}
				
				if (i==N-1) MAX = Math.max(MAX, dp[i][j]);
			}
		}
		
		System.out.println(MAX);
	}
}

 

정답!