[c++ 백준] (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. dp를 이용하여 문제를 해결했습니다.

2. 먼저 입력을 받을 배열과 dp를 활용할 배열을 선언 하였습니다. 크기는 (1 ≤ N ≤ 1,000) 만큼 선언 하였습니다.

3. dp 배열에는 입력 받은 배열로 초기화 해준 뒤 점점 증가 하는 수열 인지와 지금 까지 더한 수열이 초기화 한 수 보다 큰지를 비교하여 dp 배열에 넣어 주었습니다. 조건문(arr[j] < arr[i] && dp[i] < dp[j] + arr[i])을 이용하였습니다.

4. 다시 초기화 된 dp 배열을 비교 하여 큰 수를 MAX 변수에 넣어 주어 답을 출력 했습니다.

 

---

코드

#include<iostream>

#define endl "\n"
using namespace std;

int dp[1001] , arr[1001];
int N;

void Answer()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	int MAX = 0;
	for (int i = 0; i < N; i++)
	{
		dp[i] = arr[i];
		for (int j = 0; j < i; j++)
		{
			if (arr[j] < arr[i] && dp[i] < dp[j] + arr[i])
			{
				dp[i] = dp[j] + arr[i];
			}
		}
		MAX = max(dp[i], MAX);
	}
	cout << MAX;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	Answer();
	return 0;
}