백준
[백준] 1932번 정수 삼각형
모닝수박
2020. 5. 27. 15:17
1932번: 정수 삼각형
문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최�
www.acmicpc.net
RGB거리와 마찬가지로
1번째부터 N번째까지 밑으로 내려가며 합이 최댓값이 되는 값만 저장한다.
문제에 있는 예제로 표현해보면
이렇게 최댓값인 30이 답이 되는 것이다.
이대로 구현해주면 끝
#include <iostream>
#include <algorithm>
using namespace std;
long long triangle[501][501] = { 0 };
int main() {
int N;
cin >> N >> triangle[0][0];
for (int n = 1; n < N; n++) {
for (int i = 0; i <= n; i++) {
cin >> triangle[n][i];
if (i == 0) triangle[n][i] += triangle[n - 1][i];
else if (i == n) triangle[n][i] += triangle[n - 1][i - 1];
else triangle[n][i] += max(triangle[n - 1][i], triangle[n - 1][i - 1]);
}
}
long long Max = - 1;
for (int i = 0; i <= N; i++) Max = max(Max, triangle[N - 1][i]);
cout << Max;
return 0;
}