< 백준 BaekJoon : 1932번 정수삼각형 > C++

<< 문제 >>

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

1932번: 정수 삼각형

 

이 문제도 Dynamic Programming으로 해결할 수 있습니다. 

 

가장 큰 경로를 선택한다는 것은 결국 꼭대기에서 얻을 수 있는 최대가 되는 경우를 찾는 것이다. 

 

결국 아래부터 자신의 위치에서 최대값을 구해 올라온다면 꼭대기에서도 최대가 되는 값을 구할 수 있다.

 

이런식으로

 

<< 코드 >>

 

#include <iostream>
using namespace std;


int sum[500][500];

int main() {

	int num;
	cin >> num;

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < i+1; j++) {
			int temp;
			cin >> temp;
			sum[i][j] = temp;
		}
	}
	
	for (int i = num - 2; i >= 0; i--) {
		for (int j = 0; j < i+1; j++) {
			if (sum[i + 1][j] > sum[i + 1][j + 1]) {
				sum[i][j] += sum[i + 1][j];
			}
			else {
				sum[i][j] += sum[i + 1][j + 1];
			}
		}
	}

	cout << sum[0][0];
}

 

<< 깃헙 >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/1932.%E2%80%85%EC%A0%95%EC%88%98%E2%80%85%EC%82%BC%EA%B0%81%ED%98%95