백준 1932 정수 삼각형

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 각각 n번째 줄에 n개의 숫자가 주어지며 삼각형을 이루는데 이때 한 원소에서 다음원소로는 왼쪽 대각선이나 오른쪽 대각선으로 이동이 가능하다면 이러한 이동경로의 최대값을 구하는 문제입니다. dp를 이용하여 각각 이전 번째 줄에서의 최대값들을 갱신후 아래쪽으로 내려가야 합니다.

 

그렇다면 왼쪽 대각선과 오른쪽 대각선을 어떻게 나타낼지만 해결하면 되는 문제입니다.

 

예를들어 숫자를 적어보면 

 

    1

  2  3

4  5  6    이 있습니다. 이때 1은 [1][1]의 원소이고 2는 [2][1] 3은 [2][2] 4는 [3][1] 5는 [3][2] 6은 [3][3] 이라는것을 확인 할 수 있습니다.

따라서 n번째줄 k번째의 값은 n+1번째줄 k번째 값과 n+1번째줄 k+1번째 값으로 이동 할 수 있다는 사실을 알 수 있습니다.

따라서 아래와 같은 점화식이 생성됩니다. max가 있는 이유는 저기서 5라는 숫자가 2 와 3에 의해서 계산이 되므로 이때 더큰 값을 저장하기 위해서입니다.

dp[i+1][j] = max(dp[i+1][j], dp[i][j] + num[i+1][j]);

dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + num[i+1][j+1]); 

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int num[501][501] = {0, };
	int dp[501][501] = {0, };
	int n; cin >> n;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= i; j++)
			cin >> num[i][j];
	}
		
	
	dp[1][1] = num[1][1];
	for(int i = 1; i < n; i++) {
		for(int j = 1; j <= i; j++) {
			dp[i+1][j] = max(dp[i+1][j], dp[i][j] + num[i+1][j]);
			dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + num[i+1][j+1]);
		}
	}
	int result = 0;
	for(int i = 1; i <= n; i++) {
		result = max(dp[n][i], result);
	}
	cout<<result;
	return 0;
}