728x90
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
using namespace std;
int N;
vector<int> A;
int cache[1001];
int LIS(int start){
if(start == N){
return 0;
}
int&ret = cache[start];
if(ret != -1){
return ret;
}
ret = 1;
for(int next = start+1; next<N; ++next){
if(A[start] < A[next]){
ret = max(ret, LIS(next) + 1);
}
}
return ret;
}
int main() {
cin >> N;
memset(cache, -1, sizeof(cache));
for(int i=0; i<N; ++i){
int a;
cin >> a;
A.push_back(a);
}
int maxx = -1;
for(int i=0; i<N; ++i){
if(maxx < LIS(i)){
maxx = LIS(i);
}
}
cout << maxx;
return 0;
}
dp 문제이다.
next를 start+1부터 시작해서 끝까지 반복시켜 만약 증가되는 부분(A[next] > A[start])일 때 LIS(next)+1 과 ret을 비교해 더 큰 값을 저장한다.
728x90
반응형
'PS > DP' 카테고리의 다른 글
[2294] 동전 2 (0) | 2023.06.27 |
---|---|
[11054] 가장 긴 바이토닉 부분 수열 (0) | 2023.04.29 |
[2156] 포도주 시식 (0) | 2023.04.14 |
[10844] 쉬운 계단 수 (0) | 2023.04.14 |
[1463] 1로 만들기 (0) | 2023.04.13 |