131. 1932(정수 삼각형)

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList<Integer>[] triangle = new ArrayList[N];

		for (int i = 0; i < N; i++) {
			triangle[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split(" ");
			for (int j = 0; j < tmp.length; j++) {
				triangle[i].add(Integer.parseInt(tmp[j]));
			}
		}

		for (int i = 1; i < N; i++) {
			for (int j = 0; j < i + 1; j++) {
				if (i == 1) {
					triangle[i].set(j, triangle[i].get(j) + triangle[0].get(0));
					continue;
				}

				if (j == 0) {
					triangle[i].set(j, triangle[i].get(j) + triangle[i-1].get(0));
					continue;
				}

				if (j == i) {
					triangle[i].set(j, triangle[i].get(j) + triangle[i-1].get(j-1));
					continue;
				}
				triangle[i].set(j, triangle[i].get(j) + Math.max(triangle[i-1].get(j-1), triangle[i-1].get(j)));
			}
		}
		
		System.out.println(Collections.max(triangle[N-1]));
	}

}

문제요약

N층 까지 있는 정수 삼각형에 값을 주는데 아래층으로 내려올 때 선택된 수의 합이 최대인 경우를 구하라.

설명

다음과 같이 차례로 누적합을 구해 나가면서 최종에 도달 했을 때 최대 값을 고르면 된다.

				if (i == 1) {
					triangle[i].set(j, triangle[i].get(j) + triangle[0].get(0));
					continue;
				}

 

두번째 케이스 부터 시작하는데 맨 처음( 3과 8이 나오는 부분)에는 전에 값이 하나밖에 없으므로 그 값을 바로 더한다.

				if (j == 0) {
					triangle[i].set(j, triangle[i].get(j) + triangle[i-1].get(0));
					continue;
				}

현재 테스트 케이스의 인덱스가 0인 값은 무조건 전 케이스의 인덱스가 0인 값을 더해야 한다.

				if (j == i) {
					triangle[i].set(j, triangle[i].get(j) + triangle[i-1].get(j-1));
					continue;
				}

현재 테스트 케이스의 인덱스가 마지막인 값은 무조건 전 케이스의 인덱스의 마지막 값을 더해야 한다.

triangle[i].set(j, triangle[i].get(j) + Math.max(triangle[i-1].get(j-1), triangle[i-1].get(j)));

위에 모두 해당 되지 않는 경우 전 케이스 두 값 중 최대값을 찾아서 그 값을 더하고 덮어 씌우면 된다.