[dp] 1932 정수 삼각형

정수 삼각형 ( 1932 )

 

풀이코드

#include <iostream>
#include <algorithm>
using namespace std;
// 1932 정수 삼각형
const int MAX = 500;
int n;
int A[MAX + 1][MAX + 1];
int cache[MAX + 1][MAX + 1];

int max(int a, int b){
	return a > b ? a : b;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < i; j++){
			cin >> A[i][j];
		}
	}
	
	cache[1][0] = A[1][0];
	
	for(int i = 2; i <= n; i++){
		for(int j = 0; j <= i; j++){
			if(j == 0 || i == j) {
				cache[i][j] = cache[i - 1][j] + A[i][j];
			}
			else{
				cache[i][j] = max(cache[i - 1][j - 1], cache[i - 1][j]) + A[i][j];
			}
		}
	}
	cout << *max_element(cache[n], cache[n] + n) << '\n';
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

풀이

1. n 의 크기가 500 이 최대이다. 그렇다면 총 수의 개수는 1 ~ 500 까지의 합이 최대이다. 이것을 브루트 포스로 처리하려면 시간이 부족하다.

2. 이전에 풀었던 문제 동물원 / RGB 거리 와 접근방식이 아예 같다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

- max_element 의 사용이 편하다는 것을 알았다.