1932번 - 정수 삼각형

1️⃣ DP

 

✏️ 풀이 과정

정수 삼각형의 모양을 보고 어떤 식으로 저장해야 할 지 난감하다고 느끼기 쉽지만 다이나믹 프로그래밍을 이용하기로 마음먹으면 의외로 인덱스 0부터 순서대로 집어넣고 간단하게 해결할 수 있습니다.

 

기본 아이디어는 배열을 하나 만들고 삼각형의 꼭대기를 0번째 단계, 마지막 줄을 n-1번째 단계라 할 때 배열에 해당 단계의 해당 인덱스의 입력을 선택했을 때의 최댓값이 얼마인지를 계속 업데이트해주는 것입니다.

 

왼쪽 끝은 항상 이전 결과의 왼쪽 끝에서만 선택할 수 있고 오른쪽 끝 역시 이전 결과의 오른쪽끝에서만 선택할 수 있습니다. 그 이외의 경우에는 인덱스-1과 인덱스 위치의 결과 중 큰 것을 선택해 현재 입력에 더하면 됩니다.

 

업데이트를 마쳤다면 주어진 n 크기의 배열이 완성되었을텐데 배열에서 가장 큰 수를 찾아 출력하면 풀이가 종료됩니다. 

 

⏱ 시간 복잡도

이중 루프가 있기 때문에 시간 복잡도는 O(n^2)이 됩니다. j가 i번만 반복되기 때문에 더 낫지 않을까 생각이 들 수 있지만 실제로 횟수를 세보면 1+2+...+n = n(n+1)/2 등차수열의 합과 같기 때문에 O(n^2)이 됩니다. n이 500까지 가능하기 때문에대략 계산량 250000으로 시간 내에 해결할 수 있음을 예측할 수 있습니다. 

 

💻 코드

Java

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

public class Main{
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n];
		int[] res = new int[n];
		int[] tmp;
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			tmp = Arrays.copyOf(res, res.length);
			for(int j=0;j<i;j++) {
				input[j] = Integer.parseInt(st.nextToken());
				if(j == 0) {
					res[j] = tmp[j] + input[j];
				} else if(j == i-1) {
					res[j] = tmp[j-1] + input[j];
				} else {
					res[j] = Math.max(tmp[j-1], tmp[j]) + input[j];
				}
			}
		}
		int max = Integer.MIN_VALUE;
		for(int i=0;i<n;i++) {
			if(res[i] > max) {
				max = res[i];
			}
		}
		System.out.println(max);
		br.close();
	}
}