백준 1932 정수 삼각형(C++)

홀든콜필드 2022. 12. 27. 20:42

728x90

DP의 기본적인 문제.

프로그래머스에서는 같은 문제가 레벨3로 어려운 문제에 속했는데 백준에선 실버 판정을 받았다. 하삼각행렬로 삼각형을 저장하고 각 행렬의 숫자를 적절하게 갱신해주면 되는 문제다.

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

int DP[501][501];

int main() {

	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i < j)
				continue;
			cin >> DP[i][j];
		}
	}

	for (int i = n - 2; i > -1; i--) {
		for (int j = n - 2; j > -1; j--) {
			if (i < j)
				continue;
			DP[i][j] = max(DP[i + 1][j + 1] + DP[i][j], DP[i + 1][j] + DP[i][j]);
		}
	}

	cout << DP[0][0] << endl;
}