C++ / 백준 / 1932 / 정수 삼각형

문제

 

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

 

 

 

문제풀이

 

맨 위층부터 시작해서 아래에 있는 수를 선택해가며 내려가고, 합한 값 중 최댓값을 출력하는 문제이다.

DP를 이용해서 해당 삼각형을 편하게 2차원 벡터로 나타내면

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

이런식으로 나타낼 수 있다.

위에서 아래로 이동하므로 DP[y][x]의 값은 한 칸 위 또는 왼쪽 위 대각선 한 칸 중 큰 값을 더하면 된다.

따라서 식으로 나타내면 Arr[y][x] + DP[y-1][x-1], DP[y-1][x]이 된다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0);
	cin >> N;

	vector<vector<int>>triangle(N + 1, vector<int>(N + 1, 0));
	vector<vector<int>>DP(N + 1, vector<int>(N + 1, 0));

	for (int y = 1; y <= N; ++y) {
		for (int x = 1; x <= y; ++x) {
			cin >> triangle[y][x];
		}
	}

	for (int y = 1; y <= N; ++y) {
		for (int x = 1; x <= y; ++x) {
			DP[y][x] = triangle[y][x] + max(DP[y - 1][x - 1], DP[y - 1][x]);
		}
	}

	int answer(0);
	for (int x = 1; x <= N; ++x) {
		answer = max(answer, DP[N][x]);
	}

	cout << answer;
}