[c++] 백준 1932 정수 삼각형

백준 단계별로 풀어보기 [동적계획법1] 정수 삼각형

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

1932번: 정수 삼각형

 

[풀이]

대각선 오른쪽 위와, 왼쪽 위 중 더 큰 값과의 합을 구해 나간다.

-> path[i][j] = std::max(path[i - 1][j - 1], path[i - 1][j]) + tri[i][j];

 

[코드]

#include <iostream>
#include <string>
#include <algorithm>

int main() {
	// 정수 삼각형, 합이 최대가 되는 경로
	int n;
	int tri[502][502];
	int path[502][502];

	std::cin >> n; // 삼각형 크기
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			std::cin >> tri[i][j];
		}
	}

	path[1][1] = tri[1][1];

	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			path[i][j] = std::max(path[i - 1][j - 1], path[i - 1][j]) + tri[i][j];
		}
	}

	int m = 0;
	for (int i = 1; i <= n; i++) {
		m = std::max(m, path[n][i]);
	}

	std::cout << m;
}