[백준 알고리즘/BOJ] 자바(java) 1932번 정수 삼각형

1932번: 정수 삼각형

 

 

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

 

 

 

 

[백준 알고리즘/BOJ] 자바(java) 1149번 RGB거리

백준 1149번을 풀 수 있다면 쉽게 풀 수 있는 문제이다. 1149번과 달리 이 문제는 삼각형 모양으로 숫자가 구성되어 있기 때문에 가장 첫 열과 마지막 열은 선택지가 하나밖에 없는 것에 주의해야 한다.

package baekjoon;
import java.util.*;
import java.io.*;

public class B_1932 {
	static int n;
	static int[][] num;
	static int[][] max;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		num = new int[n][n];
		max = new int[n][n];
		StringTokenizer st;
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<=i;j++) 
				num[i][j] = Integer.parseInt(st.nextToken());
		}
		System.out.println(maxNum());
	}
	static int maxNum() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<=i;j++) {
				if(i == 0)
					max[i][j] = num[i][j];
				else {
					if(j == 0)
						max[i][j] = num[i][j] + max[i-1][j];
					else if(j == i)
						max[i][j] = num[i][j] + max[i-1][j-1];
					else
						max[i][j] = num[i][j] + Math.max(max[i-1][j-1], max[i-1][j]);
				}
			}
		}
		int m = max[n-1][0]; // max 배열의 가장 마지막 행에서 최대값 찾기
		for(int i=1;i<n;i++)
			if(m < max[n-1][i])
				m = max[n-1][i];
		return m;
	}
}