[C++/백준] 1932번-정수 삼각형

링크

---

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

문제

---

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

---

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

---

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

풀이

---

윗부분부터 순서대로 계산하는 알고리즘을 구성하면 되는 문제였다.

다음 그림에서 3, 8에 7을 더한 값을 각각 저장하면 10, 15가 된다.
다음 줄도 똑같이 더해주면 18, (11, 16), 16이 되는데 최댓값을 구하는 문제이므로 중복된 자리에서는 더 큰값을 저장해주면 된다.
따라서 18, 16, 16이 저장된다.

이와 같은 방법으로 마지막 줄까지 내려간 뒤에 그 중 최댓값을 구해주면 된다.

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	int num[500];
	int dp[500] = { 0 };
	int tmp[500] = { 0 };

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i + 1; j++) {
			cin >> num[j];
		}
		if(i==0)
			dp[0] = num[0];
		else {
			for (int j = 0; j < i; j++) {
				tmp[j] = max(tmp[j], dp[j] + num[j]);
				tmp[j + 1] = dp[j] + num[j + 1];
			}
			for (int j = 0; j < i + 1; j++) {
				dp[j] = tmp[j];
			}
		}
	}

	int result = 0;
	for (int i = 0; i < N; i++) {
		if (dp[i] > result)
			result = dp[i];
	}

	cout << result;

	return 0;
}