[백준] 정수 삼각형 (1932번)

문제

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

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

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

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

입력

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

출력

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

---

기본적인 dp문제이다.

삼각형에서 값을 더할 수 있는게 두 개이므로 그 두 값중 더 큰값을 계속해서 선택하면 된다.

정답 점화식은 dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + p[i][j]이다.

인덱스가 없는 지점이라도 0으로 초기화되기 때문에 신경쓰지않고 계산하면 값을 구할 수 있다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%A0%95%EC%88%98%20%EC%82%BC%EA%B0%81%ED%98%95%20(1932%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int N, res;
int p[501][501];
int dp[501][501];

void dynamic() {
	dp[1][1] = p[1][1];
	res = dp[1][1];
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + p[i][j];
			if (dp[i][j] > res) res = dp[i][j];
		}
	}
}

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++) 
		for (int j = 1; j <= i; j++)
			cin >> p[i][j];

	dynamic();
	cout << res;
}