BAEKJOON 1932:정수 삼각형(DP)

최대 합이 되는 경로 검색

1932번: 정수 삼각형

---

코드

 2차원 배열로 구성을 했다변 더 좋았겠지만, 2차원 배열을 굳이 사용하지 않더라도 수식만으로 2차원 배열을 사용하는 것처럼 구성이 가능하다는 것을 보이기 위해 1차원 배열을 사용해봤다.

#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;
	int* arr = new int[n * n];

	cin >> arr[0];
	for (int i = 1; i < n; ++i) {
		cin >> arr[i * n];
		arr[i * n] += arr[(i - 1) * n];
		for (int k = 1; k < i; ++k) {
			cin >> arr[i * n + k];
			if (arr[(i - 1) * n + k - 1] > arr[(i - 1) * n + k]) 
				arr[i * n + k] += arr[(i - 1) * n + k - 1];
			else arr[i * n + k] += arr[(i - 1) * n + k];
		}
		cin >> arr[i * n + i];
		arr[i * n + i] += arr[(i - 1) * n + i - 1];
	}

	int max = arr[(n - 1) * n];
	for (int i = 1; i < n; ++i) {
		if (max < arr[(n - 1) * n + i]) {
			max = arr[(n - 1) * n + i];
		}
	}

	cout << max;
	delete[] arr;
	return 0;
}

 

설명

 문제의 설명에 따라 i+1층의 계산 결과는 i층의 좌우측 값을 선택적으로 더해 구성할 수 있다.

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

 DP는 큰 문제를 작게 쪼개는 개념이니 만큼, 3층짜리 삼각형을 생각해보자.

각 배열의 시작과 끝({7}, {3, 8}, {8, 0})는 더할 수 있는 것이 정해져있다. 삼각형의 끝에 위치하기 때문이다.

 그러나 밑줄이 그어지지 않은 1의 경우 바로 윗단의 3과 8을 더할 수 있다. 중요한 점은 어디를 더해야 더 큰 수가 나오느냐는 것인데, 1과 더했을 때 더 큰 수가 되는 값을 선택하면 된다. 3이 들어간 위치를 arr[1][i - 1], 8이 들어간 위치를 arr[1][i]이라 할 때, 우리는 arr[1][i]를 선택해야한다.

if(arr[1][i - 1] < arr[1][i]){
	arr[2][i] += arr[1][i];
}else{
	arr[2][i] += arr[1][i - 1];
}

 또한, (1)1 + 3과 (2)1 + 8에 동일한 값 n을 더했을 때 (1) < (2)는 언제나 참이다. 즉, (1)은 저장할 필요가 이후에 고려할 필요가 없다.