[백준] 1932번 정수 삼각형

문제: 1932번: 정수 삼각형

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
//#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	vector<vector<int>> table(n);
	for (int i = 0; i < n; i++) {
		table[i] = vector<int>(i + 1);

		for (int j = 0; j < i + 1; j++) {
			cin >> table[i][j];
		}
	}
	// 밑에서부터 더하면서 올라가용~
	for (int i = n - 2; i >= 0; i--) {
		for (int j = 0; j < i + 1; j++) {
			table[i][j] += max(table[i + 1][j], table[i + 1][j + 1]);
		}
	}
	cout << table[0][0]; // 출력~

	return 0;
}

 

밑에서부터 더하면서 올라가면 쉽게 해결할 수 있는 문제이다. 더할 때는 자신의 대각선 아래 요소 중 큰 값을 더해주면 된다.

 

위 행위를 다 마친 후의 table[0][0] 의 값이 바로 가장 큰 값을 가지는 경로의 합이다.