[백준 / C++] 가장 큰 증가하는 부분 수열 (실버2, 11055)

문제

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

예제 입력 1

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1

113

---

문제 풀이

이번 문제는 주어진 수열 A에서 증가하는 부분 수열 중 가장 큰 합을 구하는 문제입니다.

 

일반적인 방식으로 생각한다면 모든 칸을 순회하며 자기보다 큰 칸을 탐색하고, 해당 값을 누적하는 방식으로도 풀 수 있으나, 문제에서 주어진 수열의 최대 길이가 1000이므로 시간 초과가 나오게 됩니다.

 

즉, 현재 칸에서 얻을 수 있는 최대값을 저장해두고, 그보다 낮은 수가 나오는 경우는 전부 가지치기를 해주며 다음 칸으로 이동해주는 방식으로 문제에 접근할 수 있습니다.

 

저의 경우 재귀 방식을 사용해 전체를 탐색하며 DP 배열에 현재 칸에서의 최대값을 저장하였고, 그보다 큰 수가 나오는 경우로만 반복해서 탐색을 진행하는 방식으로 문제를 해결하게 되었습니다.

 

처음에는 무조건 현재 칸보다 큰 수로만 탐색을 진행하였으나, 그 결과 첫 번째 수가 무조건 포함되는 가장 큰 수가 나왔으며 2번의 실패를 받았고 이후 로그를 찍어보며 모든 수로 분기하는 방식으로 수정하여 문제를 해결 하였습니다.

코드

#include <iostream>

using namespace std;

int n;
int arr[1002];
int DP[1002];

void Go(int num, int sum)
{
	if (num == n - 1)
	{
		DP[n - 1] = max(DP[n - 1], sum);
		return;
	}

	if (DP[num] != 0 && DP[num] >= sum) return;

	DP[num] = sum;

	for (int i = num + 1; i < n; i++)
	{
		if (arr[num] < arr[i])
		{
			Go(i, sum + arr[i]);
		}
		else
		{
			Go(i, arr[i]);
		}
	}
}

int main()
{
	// 입력
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int temp = 0;
		cin >> temp;

		arr[i] = temp;
	}

	Go(0, arr[0]);

	int mx = -1;

	for (int i = 0; i < n; i++)
	{
		mx = max(DP[i], mx);
	}

	cout << mx;
}