DP - 1932. 정수 삼각형

문제

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

잠깐만

맨 아래층에서부터 위층까지 올라가볼까요?

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int size = Integer.parseInt(st.nextToken()); 
		
		int[][] values = new int[size][size];
		for (int y = 0; y < size; y++) {
			st = new StringTokenizer(br.readLine());
			for (int x = 0; x < y+1; x++) {
				values[y][x] = Integer.parseInt(st.nextToken());
			}	
		}
		
		for (int y = size-2; y >= 0; y--) {
			for (int x = 0; x <= y; x++) {
				values[y][x] = values[y][x] + Math.max(values[y+1][x], values[y+1][x+1]);
			}	
		}	
		
		System.out.print(values[0][0]);
	}
}

 

설명

위층에서 아래층으로 계산해 나갈수도 있지만, 범위 제한을 추가해야하기 때문에, 번거로울수 있다 생각합니다.

그래서, 아래층에서부터 올라가볼게요. 오히려 범위 제한이 없어, 코드 구할때도 편할거에요.

로직도 쉬워지는데, 아래층의 연속된 값의 max값을 구하고, 윗층으로 올려보내주면 됩니다.

 

회고

최대값 구하기에 대한 DP 문제에 자신감 좀 붙으셨나요?