c++ 백준 1932번 문제

[Silver I] 정수 삼각형 - 1932

문제 링크

성능 요약

메모리: 2020 KB, 시간: 8 ms

분류

다이나믹 프로그래밍

문제 설명

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

풀이

배열이나 벡터에 값을 저장하지 않고 값을 받는 즉시 계산을 하여 시간을 줄였다. 계산이 끝나면 오름차순으로 sort를 하여 가장 큰 값을 출력한다

#include <iostream>
#include <algorithm>

using namespace std;

bool desc(int a, int b) {
	return a > b;
}
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int arr[502];
	int ans[502];
	int tmp;
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			cin >> tmp;			
			if (n == 1) {
				cout << tmp;
				return 0;
			}
			if (i == 1)
			{
				arr[j] = tmp;
				ans[j] = tmp;
				continue;
			}
			if (j == 1) {
				arr[j] = ans[j] + tmp;
			}
			else if (j == i) {
				arr[j] = ans[j - 1] + tmp;
			}
			else {
				arr[j] = max(ans[j - 1], ans[j]) + tmp;
			}			
		}
		for (int k = 1; k <=i; k++)
		{
			ans[k] = arr[k];
		}
	}
	sort(ans + 1, ans + n + 1,desc);

	cout << ans[1];
}