BOJ 백준 11055 가장 큰 증가 부분 수열 <LIS>

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

< 가장 큰 증가 부분 수열 >

가장 큰 증가 부분 수열 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	9809	4414	3587	46.603%

문제

수열 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

 이 문제는 백준 11053번 문제 ( https://www.acmicpc.net/problem/11053 ) 가장 긴 증가하는 부분 수열을 풀 줄 안다면 풀 수 있는 문제이다.

11053 풀이) https://onecoke.tistory.com/24?category=789163

11053번은 숫자의 합은 생각하지 않고 증가하는 부분 수열의 원소의 개수가 가장 큰 경우를 출력해주는 거라면 

가장 큰 증가하는 부분 수열 문제는 원소의 개수가 하나여도 그 원소의 값이 다른 증가하는 부분 수열 원소들의 합보다 크다면

원소 한 개가 답이 될 수 있다.

즉, 예시에서 원소의 개수가 가장 많은 경우는 1 - 2 - 3 - 5 - 6 - 7 - 8 로 7개이지만,

원소의 합이 가장 큰 경우는 1 - 2 - 50 - 60 으로 원소가 4개지만 합이 113이므로 113이 답이 된다.

즉 원소의 개수가 아닌 원소들의 합을 기준이 되므로, for문을 돌면서 각 원소들이 마지막 원소일 때에

합이 가장 큰 경우가 몇인 지를 dp배열에 넣어주면 된다.

for i=0 ~ n - 1  // i번째 원소가 마지막 원소라고 가정

for j=0 ~ i - 1 // 0부터 i - 1까지 돌면서 arr[i]보다 작은 원소를 찾기

if( arr[i] > arr[j] && dp[i] < dp[j] + arr[i] ) // arr[i]가 arr[j]보다 크고, dp[i]가 dp[j] + arr[i]보다 작은 경우 값 갱신

dp[i] = dp[j] + arr[i];

dp[i] = dp[j] + arr[i] 의 의미는 아래와 같다.

* j번째 원소가 마지막 원소일 때의 총 합과 i번 원소의 합을 더한 값을 dp[i]에 넣어준다.

이렇게 값을 갱신되는 것은 arr[i]가 arr[j]보다 큰, 즉 증가하는 수열이어야 하고 지금까지 계산했던 dp[i]의 값이

새롭게 계산한 dp[j] + arr[i]보다 작을 경우에만 이루어진다.

#include <iostream>
#define SIZE 1001

using namespace std;

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

	int arr[SIZE] = { 0 };
	int dp[SIZE] = { 0 };

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}

	for (int i = 0; i < n; ++i)
	{
		dp[i] = arr[i];
		for (int j = 0; j < i; ++j)
		{
			if (arr[i] > arr[j] && dp[i] < dp[j] + arr[i])
			{
				dp[i] = dp[j] + arr[i];
			}
		}
	}
	int iMax = -1;
	for (int i = 0; i < n; ++i)
	{
		if (iMax < dp[i]) iMax = dp[i];
	}
	cout << iMax << '\n';

	return 0;
}