백준 1932번: 정수 삼각형

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

1932번: 정수 삼각형

 

 

0. 알고리즘 분류

 다이나믹 프로그래밍

 

 

1. 문제

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

 

2. 풀이

 또 DP 문제다. 1149번의 "RGB 거리"와 매우 유사하다. 모양이 삼각형일 뿐. 우선 삼각형의 정수값을 받아들일 배열로 삼각형 모양으로 동적 배열을 사용했다. 그냥 2차원 배열을 써도 문제는 없지만, 될 것 같아서 그냥 했다.

 

 위에서부터 저장된 dp배열 두 값 중 최댓값을 dp배열에 저장하고 아래의 값을 더하면 된다. 하지만, 제일 왼쪽과 오른쪽변의 정수는 하나의 정수만을 받는다. 따라서 이를 염두에 두고 코딩한다.

 

 

3. 코드

#include <iostream>

using namespace std;

int max(int x, int y) {
	return (x > y) ? x : y;
}

int main(void) {
	int n;
	cin >> n;
	
	int** tri = new int*[n];
	int** dp = new int*[n];
	for (int i = 0; i < n; i++) {
		tri[i] = new int[i+1];
		dp[i] = new int[i+1];
		
		for (int j = 0; j <= i; j++) {
			cin >> tri[i][j];
		}
	}
	
	dp[0][0] = tri[0][0];
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0) {
				dp[i][j] = tri[i][j] + dp[i-1][j];
			}
			else if (j == i) {
				dp[i][j] = tri[i][j] + dp[i-1][j-1];
			}
			else {
				dp[i][j] = tri[i][j] + max(dp[i-1][j-1], dp[i-1][j]);
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (ans < dp[n-1][i]) {
			ans = dp[n-1][i];
		}
	}
	cout << ans;
	
	for (int i = 0; i < n; i++) {
		delete tri[i];
		delete dp[i];
	}
	delete tri;
	delete dp;
	
	return 0;
}