BOJ 1932 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

 

문제 분석

- dp 문제이다.

- 메모이제이션을 이용하여 경로의 최대값을 저장 후 마지막 도착 행에서 최대값을 출력한다. (마지막 점이 최대값이 아님에 주의한다)

 

 

문제 풀이

1) 삼각형의 모양을 배열에 입력받는다.

2) dp배열(최대 누적 합)의 시작좌표의 값을 초기화해준다. 

3) 행은 1부터 N까지 탐색하고 열은 0부터 행의 값보다 작거나 같은 경우만 탐색한다.

4) 일단 아래 행에다가 바로 위의 행(dp)의 값과 현재 좌표의 값(map)을 더하여 넣는다.

5) 만약 대각선 왼쪽 위의 범위가 배열의 범위를 벗어나지 않는다면 대각선 왼쪽 위의 값과 비교하여 더 큰 값을 삽입한다.

6) 마지막 배열의 행에서 정렬 작업을 해주고 거기서 가장 큰 값을 출력한다.

 

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

public class Main {

	private static int[][] map; // 삼각형
	private static long[][] dp; // 경로 저장

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		dp = new long[N][N];

		for (int i = 0; i < N; i++) { // 입력
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j <= i; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 입력-end

		dp[0][0] = map[0][0]; // 시작좌표 초기화

		for (int i = 1; i < N; i++) { // 1행엔 0행 값 더하기 위해 인덱스 1부터 시작
			for (int j = 0; j <= i; j++) {
				dp[i][j]=dp[i-1][j]+map[i][j];
				if(j-1<0)
					continue;
				dp[i][j] = Math.max(dp[i][j], map[i][j]+dp[i-1][j-1]);
			}
		}
		
		 Arrays.sort(dp[N-1]);
	     System.out.println(dp[N-1][N-1]);

	}// main

}// class-end