백준1932 - 정수 삼각형

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

1932번: 정수 삼각형

2차원 DP문제이다. 하지만 자료형의 크기가 500*500이여서 메모리초과가 날 것 같아 벡터를 사용하여 DP를 계산하였더니 조금 복잡해졌다. 

 

다음은 정수 삼각형을 표현한 그림이다. 정수 삼각형은 2차원 배열을 사용하였다.

정수 삼각형(2차원 배열)

 

다음은 정수 삼각형에서 DP값을 추출한 그림이다. DP 값은 벡터를 사용하였다.

DP 결과(벡터)

 

그림을 보면 정수 삼각형과 DP 결과의 2번째 인덱스 차이가 1씩 나는 것을 알 수 있다.  정수 삼각형을 입력 받을 때 인덱스로 0을 사용하지 않았다. 그렇기 때문에 벡터를 사용하고 인덱스를 0으로 사용하지 않고 푼다면 이 점을 주의해야 한다. 

 

 

다음은 DP를 추출한 방법이다.

ex1.) DP[31] : 정수 삼각형[3][2]의 DP값, 정수 삼각형[2][1]의 DP값(DP[2][0])과 정수 삼각형[2][2]의 DP값(DP[2][1])의 크기를 비교하여 큰 값을 구한 뒤 정수 삼각형[3][2]를 더한 뒤 벡터에 넣어준다.

 

ex2.) DP[41] : 정수 삼각형[4][2]의 DP값, 정수 삼각형[3][1]의 DP값(DP[3][0])과 정수 삼각형[3][2]의 DP값(DP[3][1])의 크기를 비교하여 큰 값을 구한 뒤 정수 삼각형[4][2]를 더한 뒤 벡터에 넣어준다.

 

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

int main() {
	int mat[501][501]; //정수 삼각형의 입력한 숫자
	int n; //정수 삼각형의 높이
	int ans = -1; //답
	vector<int> v[501]; //정수 삼각형의 DP 결과 값

	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {

			cin >> mat[i][j];
		}
	}

	v[1].push_back(mat[1][1]); //첫번째 DP값 설정

	//2번째 높이부터 계산, 모든 숫자는 DP값을 기준으로 비교하고 더한다.
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if (j == 1) { //첫번째 숫자
				v[i].push_back(v[i - 1][j - 1] + mat[i][j]); //자신을 기준으로 오른쪽 대각선 위에 숫자를 더한다.
			}
			else if (j == i) { //맨 마지막 숫자
				v[i].push_back(v[i - 1][j - 2] + mat[i][j]); //자신을 기준으로 왼쪽 대각선 위에 숫자를 더한다.
			}
			else { //그 외의 경우
				int big; //DP값으로 넣어줄 숫자
				big = max(v[i - 1][j - 2], v[i - 1][j - 1]); //자기 자신을 기준으로 왼쪽 대각선 위와 오른쪽 대각선 위의 숫자 크기를 비교한다.
				big = big + mat[i][j]; //자기 자신을 더한다.
				v[i].push_back(big); //DP값으로 갱신한다.
			}
		}
	}

	//가장 큰 DP값을 찾으면 되니까 최고 높이에 있는 원소들만을 비교하여 가장 큰 값을 찾는다.
	for (int i = 0; i < v[n].size(); i++) {
		if (ans < v[n][i]) {
			ans = v[n][i];
		}
	}

	cout << ans;
}