[백준] 1932번 : 정수 삼각형(JAVA)

Dynamic Programming is fun!

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

1932번: 정수 삼각형

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 14단계

 

동적 계획법 1의 카테고리에 포함되어 있는 문제이다.

 

점점 문제푸는 실력이 늘어가는 것 같아 뿌듯하다

 

문제를 해결할 때, 더 나은 문제풀이 방식이 떠올라서 두가지 해결방법을 첨부한다.

 

먼처 첫 번째로는 위에서 내려오면서 최대값들을 더한 후,

 

마지막에 비교를 통해 결과값을 출력하는 방식이며

 

두 번째 방법은 삼각형의 N-1 번째 줄에서 부터 아래에서 위로 더해가는 방식으로

 

첫 번째 줄에 최대값이 저장되어 출력하는 방식이다.

 

물론 첫 번째 방식보다 두 번째 방식이 마지막에 비교를 하는일이 없어

 

시간적으로 더 빠를 것이라 생각하였지만 삼각형의 크기가 최대 500이여서

 

아마 삼각형의 크기가 더 컸다면 두 번째 방식이 시간적으로 더 나을것이다.

 

첫 번째 방식

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

public class Question_1932_1 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] Triangle = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			String[] Input = br.readLine().split(" ");
			for(int j = 0; j < Input.length; j++) {
				Triangle[i][j] = Integer.parseInt(Input[j]);
			}
		}
		
		for(int i = 1; i < N; i++) {
			Triangle[i][0] += Triangle[i-1][0];
			Triangle[i][i] += Triangle[i-1][i-1];
			for(int j = 1; j < i; j++) {
				Triangle[i][j] += Math.max(Triangle[i-1][j-1], Triangle[i-1][j]);
			}
		}
		
		int Result = Triangle[N-1][0];
		
		for(int i = 0; i < N; i++) {
			if(Result < Triangle[N-1][i])
				Result = Triangle[N-1][i];
		}
		System.out.println(Result);
	}
}

 

두 번째 방식

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

public class Question_1932_2 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] Triangle = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			String[] Input = br.readLine().split(" ");
			for(int j = 0; j < Input.length; j++) {
				Triangle[i][j] = Integer.parseInt(Input[j]);
			}
		}
		
		for(int i = N-2; i >= 0; i--) {
			for(int j = 0; j <= i; j++) {
				Triangle[i][j] += Math.max(Triangle[i+1][j], Triangle[i+1][j+1]);
			}
		}
		System.out.println(Triangle[0][0]);
	}
}