[백준 / C++] 1932번: 정수 삼각형 (dp, 다이나믹 프로그래밍)

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

1932번: 정수 삼각형

난이도: solved.ac 실버 1

 

알고리즘 분류

다이나믹 프로그래밍 (dp)

 

접근 방법

맨 윗 칸부터 아래로 내려가면서 선택한 수의 합이 최대가 되어야 한다

arr[i][j]를 선택할 때, arr[i-1][j-1] 와 arr[i-1][j]를 선택했을 때 중 합이 더 큰 걸 골라야 한다

 

 

#include <bits/stdc++.h>
using namespace std;
 
int previ[501], pres[501];
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, i, k;
	cin >> n;
	for (k = 1; k <= n; k++) {
		for (i = 1; i <= k; i++) {
			cin >> pres[i];
			pres[i] = max(previ[i - 1], previ[i]) + pres[i];
		}
		copy(begin(pres), end(pres), begin(previ));
	}
	cout << *max_element(begin(pres),end(pres));
}