백준 Silver 2 가장 큰 증가하는 부분 수열

가장 큰 증가하는 부분 수열 (백준 Silver 2)

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

LIS 중 ‘가장 합’이 큰 수열의 그 합을 구하는 문제

풀이 방식

점화식 정의
DP[n] : n을 포함하는 가장 큰 증가하는 부분 수열의 값

따라서 DP[n]은 n->0 까지 돌며
이전 노드 중
자신보다 ‘수열의 값’이 작은 노드를 찾고

DP[n] = max(DP[n], DP[Target] + 수열 N의 값)
을 적용하면 된다

이걸 1-> n까지 반복하며
마지막에 dp에서 max_element를 통해 최댓값을 구한다
(실제로는 각 요소들에 대한 반복문은 한번만 돌기에
시간 복잡도는 O(N^2)가 된다)

(재귀 * 재귀 외부에서 각 요소를 반복문)

(ex : dp[n] -> recur(target)인 경우
target은 n보다 작으며 이미 dp를 구해놓음)

제출 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int recur(const vector<int>& vec, vector<int>& dp,int start)
{
	if (start < 0)
		return 0;

	if (dp[start] != 0)
		return dp[start];

	dp[start] = vec[start];
	
	for (int i = start - 1; i >= 0; i--)
	{
		if (vec[start] > vec[i])
		{
			// start가 자신 이전 위치에서
			// 자신보다 낮은값 발견 시,
			// 그 dp값을 자신에게 더함
			dp[start] = max(dp[start], recur(vec, dp, i) + vec[start]);
		}
	}

	return dp[start];
}

int main()
{
	int n;
	cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; i++)
		cin >> vec[i];

	// 가장 '합'이 큰 LIS 의 합 구하기
	vector<int> dp(n);
	dp[0] = vec[0];

	// start = 0 ~ n까지 진행
	for (int i = 1; i < n; i++)
		recur(vec, dp, i);

	cout << *max_element(dp.begin(), dp.end());

	return 0;
}

결과

컴파일 에러는 include를 하지 않았기에….
(max_element)

LIS 는 DP 강의를 들을 때
푸는 법을 기억해 놓았기에 다행히 어렵지 않게 풀 수 있었다