1932번 정수 삼각형

문제링크 : www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

---

<알고리즘>

  동일한 계산을 반복하는 것을 막기 위해(동적 계획법) 위에서 부터 아래로 계산해 내려감

  1) 0번째줄은 변동될 사항이 없으므로 생략. 1번째 줄 부터 윗줄로부터 영향을 받아 변경될 수 있는 수 중 가장 큰 수로 값 변경

    1-1) 매 줄의 0번째 값은 바로 윗줄의 0번째 값으로만 영향을 받음

    1-2) 매 줄의 마지막 값은 바로 윗줄의 마지막 값으로만 영향을 받음

    1-3) 그 외의 값들의 윗 줄의 대각선 두 값중 큰 값을 골라서 더함

  2) 매 줄의 매 칸마다 계산하는 동안 max값과 비교하여 가장 큰 값 찾기

 

 

 

메모리 : 2940KB    메모리 44ms

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N = 0;
	cin >> N;

	vector<vector<int>> triangle(N, vector<int>(N));
	int a = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> a;
			triangle[i][j] = a;
		}
	}
	
	int max = 0;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= i;j++) {
			if (j == 0) {
				triangle[i][j] += triangle[i - 1][0];
			}
			else if (j == i) {
				triangle[i][j] += triangle[i - 1][j - 1];
			}
			else {
				//윗라인 대각선의 두 수 중 큰 쪽 선택
				triangle[i][j] += ((triangle[i - 1][j - 1] >= triangle[i - 1][j]) ? triangle[i - 1][j - 1] : triangle[i - 1][j]);
			}
			if (max <= triangle[i][j]) max = triangle[i][j];
		}
	}

	cout << max << "\n";
	
	return 0;
}