[백준 / BOJ] 1932번: 정수 삼각형

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

1932번: 정수 삼각형

 

---

 

코드

---

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

int main() {
	int n, val, sum[501][501] = {}, m = 0;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			scanf("%d", &val);
			sum[i][j] = max(sum[i - 1][j - 1], sum[i - 1][j]) + val;
		}
	}

	for (int i = 1; i <= n; i++) {
		if (sum[n][i] > m) m = sum[n][i];
	}

	printf("%d", m);
	return 0;
}

 

 

 

---

 

 

1149 RGB거리 문제와 풀이 방법이 비슷하다. 다만, 직사각형 모양의 입력 자료에서 정삼각형 모양으로 변했을 뿐이다. i행 j열 숫자의 경로 최댓값은 max(i-1행 j-1열 경로 최댓값, i-1행 j열 경로 최댓값) + (i행 j열의 수) 이다.