[백준 11055번] 가장 큰 증가하는 부분 수열

문제 링크: https://www.acmicpc.net/problem/11055

11055번: 가장 큰 증가하는 부분 수열

<문제 풀이> 다이나믹 프로그래밍(DP) 알고리즘

 

기본적인 LIS 알고리즘을 구현하면 되는 문제입니다.

 

dp는 아래와 같이 정의할 수 있습니다.

 

dp[i] : i 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것

 

dp[i]를 갱신하는 방법은 1부터 i -1까지의 dp[j]에 각각에 대해 i 번째 원소를 포함했을 때 그 합이 가장 큰 것으로 갱신해 주면 됩니다.

 

dp[1] + seq[i] : 1 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것 + i 번째 원소의 값

dp[2]  + seq[i]: 2 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것 + i 번째 원소의 값

.

.

dp[j] + seq[i] : j 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것

.

.

dp[i - 1] + seq[i] : i -1 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것

 

 

	for (int i = 1; i <= n; i++) {
		dp[i] = seq[i]; // 처음에는 자기 자신만 고려
		for (int j = 1; j < i; j++) {
			if (seq[i] <= seq[j]) continue;
			dp[i] = max(dp[i], dp[j] + seq[i]);
		}
	}

 

 

 

 

 

<C++소스코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int n;
int dp[1001];
int seq[1001];
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> seq[i];
    }
    for (int i = 1; i <= n; i++) {
        dp[i] = seq[i]; // 처음에는 자기 자신만 고려
        for (int j = 1; j < i; j++) {
            if (seq[i] <= seq[j]) continue;
            dp[i] = max(dp[i], dp[j] + seq[i]);
        }
    }
    cout << *max_element(dp, dp + n + 1);
    return 0;
}