C++ 알고리즘 - 백준 1932 정수 삼각형

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

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

/******** 전역변수 ********/


/******** 함    수 ********/


int main(void) {
	/******** C++ INIT ********/
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	/******** 지역변수 ********/
	int input1;
	int input2;
	int pos;
	int idx;
	vector<int> v;


	/******** 구    현 ********/
	cin >> input1;

	// 점화식 : 2층 까지 수 벡터에 미리 삽입 (각 위치에 가능한 최대값으로 삽입)
	cin >> input2; v.push_back(input2);
	cin >> input2; v.push_back(v[0] + input2);
	cin >> input2; v.push_back(v[0] + input2);

	// 1층이면 0번째
	if (input1 == 1) {
		cout << v[0];
		return 0;
	}

	// 2층이면 1번째, 2번째 중 맥스
	if (input1 == 2) {
		cout << max(v[1], v[2]);
		return 0;
	}

	// pos : 층에 위치 가능한 숫자 개수
	// idx : 층
	pos = 3;
	idx = 3;

	// 3층부터 최대값 계산 시작
	for (int i = 2; i < input1; i++) {
		for (int j = pos; j < idx + pos; j++) {
			cin >> input2;

			// 삼각형에서 가장 좌측 값 계산
			if (j == pos)
				v.push_back(v[pos - idx + 1] + input2);

			// 삼각형에서 가장 우측 값 계산
			else if (j == idx + pos - 1)
				v.push_back(v[pos - 1] + input2);

			// 중간 값들 계산
			else
				v.push_back(max(v[j - idx] + input2, v[j - idx + 1] + input2));
		}

		// 다음 층에 가능한 숫자 개수, 층수 재조정
		pos += idx;
		idx++;
	}

	// 가장 아래 층수의 MAX 값이 정답
	cout << *max_element(v.end() - input1, v.end());
}