[Silver 1] 1932번 정수 삼각형

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

1932번: 정수 삼각형

 

이 문제는 DP를 통해 해결할 수 있다.

 

알고리즘은 다음과 같다.

• 삼각형의 최대 크기는 500까지이다. 따라서 501x501크기의 배열을 선언하여 삼각형의 비용을 저장한다.
• DP를 위한 배열은 삼각형의 크기와 동일하게 선언한다. (모든 경로의 비용을 계산하기 위해)
• dp 배열의 첫번째 경로와 두번째 경로를 저장한다.
• 반복을 통해 왼쪽 경로와 오른쪽 경로를 계속해서 저장한다. 
• 겹치는 노드가 있기 떄문에 max 함수를 통해 최대 값인 경우를 저장한다.
  • max 함수는 위아래 모두 있을 필요 없다. (실수)
  • dp[i][j]인 경우만 max를 통해 겹치는 노드를 검사해도 된다.

 

#include <iostream>
using namespace std;
int N;
int arr[501][501];
int dp[501][501];


int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> arr[i][j];
		}
	}
	dp[0][0] = arr[0][0];
	dp[1][0] = dp[0][0] + arr[1][0];
	dp[1][1] = dp[0][0] + arr[1][1];


	for (int i = 2; i < N; i++) {
		for (int j = 0; j < i; j+=1) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j] + arr[i][j]);
			dp[i][j + 1] = max(dp[i][j + 1], dp[i - 1][j] + arr[i][j + 1]);
		}
	}
	int result = 0;
	for (int i = 0; i < N; i++)
		result = max(result, dp[N - 1][i]);

	cout << result << '\n';
}