[백준11055] 가장 큰 증가 부분 수열 (C++)

BOJ 바로가기

#include <iostream>
using namespace std;
int a[1001], d[1001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		d[i] = a[i];
		for (int j = 1; j < i; j++) {
			if (a[i] > a[j] && d[i] < d[j] + a[i])
				d[i] = d[j] + a[i];
		}
	}
	int max;
	for (int i = 1; i <= n; i++) {
		if (i == 1)
			max = d[i];
		else {
			if (d[i] > max)
				max = d[i];
		}
	}
	cout << max;
	return 0;
}

가장 긴 증가 부분 수열 / 가장 큰 증가 부분 수열
이런 타입 문제가 내겐 어렵게 느껴진다 ㅠ

📌아이디어

d[i]=d[j]+a[i]
d[j]는 d[i] 이전의 가장 큰 증가 부분 수열이다. i보다 작은 수 j에 대해 a[j]보다 a[i]가 큰 경우 가능한 한 가장 큰 d[j]에 a[i]를 더해주면 d[i]를 구할 수 있다.