티스토리 뷰
#include <iostream>
using namespace std;
int d[1001];
int a[1001];
int main(void) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
//d[i]는 a[i]를 포함하는 가장 긴 감소하는 부분 수열의 길이
d[1] = a[1];
int max = 0;
for (int i = 2; i <= n; i++) {
d[i] = 1;
for (int j = 1; j<i; j++) {
if (a[j]>a[i] && d[i]<d[j] + 1) {
d[i] = d[j] + 1;
}
}
if (max<d[i])
max = d[i];
}
cout << max << endl;
return 0;
}
'백준 알고리즘 기초 강좌' 카테고리의 다른 글
3장 다이나믹 프로그래밍 - (4) 문제 풀이 5 [1912번 - 연속합] (0) | 2017.08.20 |
---|---|
3장 다이나믹 프로그래밍 - (4) 문제 풀이 4 [11054번 - 가장 긴 바이토닉 부분 수열] (0) | 2017.08.20 |
3장 다이나믹 프로그래밍 - (4) 문제 풀이 2 [11053번 - 가장 큰 증가하는 부분 수열] (0) | 2017.08.18 |
3장 다이나믹 프로그래밍 - (4) 문제 풀이 1 [11053번 - 가장 긴 증가하는 부분 수열] (0) | 2017.08.18 |
3장 다이나믹 프로그래밍 - (3) 문제 풀이 5 [2156번 - 포도주 시식] (0) | 2017.08.17 |