#1932 : 정수 삼각형

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

 

2022.03.24

i번째 수에 도착할 때까지 도출할 수 있는 가장 큰 합의 값을 dp[i]에 저장하는 1차원 정수 배열 dp를 만든다.

dp를 완성한 뒤,

dp의 데이터 중 삼각형의 가장 아래층에 해당하는 것들만 빼내온 뒤

그 중 최댓값을 화면에 출력하면 해결된다.

 

이 dp를 만드는 방법은 다음과 같다.

 

삼각형에 속한 모든 수는

자신의 오른쪽 위 또는 왼쪽 위 중 하나를 선택하여야 한다.

 

따라서, 1층과 2층에 대하여는 다음과 같이 직접 dp 값을 넣어주고,

dp[1] = arr[1];

dp[2] = dp[1] + arr[2];
dp[3] = dp[1] + arr[3];

3층부터 마지막 층까지는 다음과 같은 반복문을 돌려주면 된다.

for(int i = 3; i<n+1; i++) {
	int this_left = (((i-1)*i)/2)+1;	//이번 층의 가장 왼쪽 요소의 인덱스
	int prev_left = ((i-2)*(i-1)/2)+1;	//위층의 가장 왼쪽 요소의 인덱스
    
	//가장 왼쪽 요소(무조건 위층의 가장 왼쪽 요소를 거침)
	dp[this_left] = dp[prev_left] + arr[this_left];
    
	//중간의 요소들
	for(int j = this_left+1; j<this_left+i-1; j++) {
		//자신의 왼쪽 위와 오른쪽 위 중 dp값이 큰 쪽을 거쳐야 함
		dp[j] = Math.max(dp[j-i], dp[j-i+1]) + arr[j];
	}
    
	//가장 오른쪽 요소(무조건 위층의 가장 오른쪽 요소를 거침)
	dp[this_left+i-1] =dp[prev_left+i-2] + arr[this_left+i-1];
}

주의할 점이 있다. 문제를 보면 삼각형의 층 수의 최솟값이 1이다.

그러므로, ArrayIndexOutOfBounds 오류가 발생하지 않도록, 2층 이상을 다루는 코드들은 모두 조건문 처리를 해주어야 한다.

 

코드

Java(2022.03.24)

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{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//삼각형의 층 수 읽어오기
		int n = Integer.parseInt(br.readLine());
		
		//삼각형에 포함된 수들의 총 개수
		final int nums = ((n*(n+1))/2);
		
		//삼각형의 내용을 저장할 정수 배열
		int[] arr = new int[nums +1];
		
		//삼각형의 내용 읽어오기
		int idx = 1;
		for(int i = 1; i<n+1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			while(st.hasMoreTokens()) arr[idx++] = Integer.parseInt(st.nextToken());
		}
		
		//dp를 위한 배열
		int[] dp = new int[nums +1];
		
		//1층과 2층의 dp값은 미리 지정해주기
		dp[1] = arr[1];
		//삼각형의 크기의 최솟값이 1이므로, 2층부터는 조건문 안에 넣어줘야 한다(안 그러면 오류가 발생함)
		if(n>1) {
			dp[2] = dp[1] + arr[2];
			dp[3] = dp[1] + arr[3];
			
			if(n>2) {
				//3층부터 dp 배열 채우기
				for(int i = 3; i<n+1; i++) {
					int this_left = (((i-1)*i)/2)+1;	//이번 층의 가장 왼쪽 요소의 인덱스
					int prev_left = ((i-2)*(i-1)/2)+1;	//위층의 가장 왼쪽 요소의 인덱스
					//가장 왼쪽 요소
					dp[this_left] = dp[prev_left] + arr[this_left];
					//중간의 요소들
					for(int j = this_left+1; j<this_left+i-1; j++) {
						//자신의 왼쪽 위와 오른쪽 위 중 dp값이 큰 쪽을 거쳐야 함
						dp[j] = Math.max(dp[j-i], dp[j-i+1]) + arr[j];
					}
					//가장 오른쪽 요소
					dp[this_left+i-1] =dp[prev_left+i-2] + arr[this_left+i-1];
				}

			}
		}


		//dp 배열 중 가장 아래층에 해당하는 부분을 가져오기
		int[] bottom = new int[n];
		for(int i = 0; i<n; i++) {
			bottom[i] = dp[nums - i];
		}
		//마지막 층 숫자 중 최댓값을 화면에 출력
		Arrays.sort(bottom);
		System.out.print(bottom[n-1]);

	}

}