728x90
https://www.acmicpc.net/problem/11054
문제
수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.
수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 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][1001][2];
int LIS(int start, int before, int isDec){
if(start == N){
return 0;
}
int& ret = cache[start][before][isDec];
if(ret != -1){
return ret;
}
ret = 0;
// 그냥 넘어갈 때
ret = LIS(start+1, before, isDec);
// 증가하고 있다면
if(isDec == 0){
if(before < A[start]){
ret = max(LIS(start+1,A[start], 0)+1, ret);
}
else if(before > A[start]){
ret = max(LIS(start+1, A[start], 1)+1, ret);
}
}
//감소하고 있다면
else if(isDec == 1){
if(before > A[start]){
ret = max(ret, LIS(start+1,A[start], 1)+1);
}
}
return ret;
}
int main() {
cin >> N;
int ans = -1;
memset(cache, -1, sizeof(cache));
for(int i=0; i<N; ++i){
int a;
cin >> a;
A.push_back(a);
}
cout << LIS(0, 0, 0);
return 0;
}
몇시간 끙끙 앓다가 결국 답을 보고 푼 문제이다.... (답 출처 : https://sbl133.tistory.com/39)
여러가지 경우를 나눠서 풀어줬는데 cache 배열에 정보를 세개나 전달해줬다는게 좀 맘에 걸리긴 한다...
그냥 LIS문제의 코드에서 반복문을 쓴 걸 좀 활용해주면 더 간결하게 풀 수 있을 것 같은데 나중에 다시 해보고 좀 간결한 답이 나오면 재포스팅 해야겠다
728x90
반응형
'PS > DP' 카테고리의 다른 글
[2133] 타일 채우기 (0) | 2023.06.27 |
---|---|
[2294] 동전 2 (0) | 2023.06.27 |
[11053] 가장 긴 증가하는 부분 수열 (0) | 2023.04.16 |
[2156] 포도주 시식 (0) | 2023.04.14 |
[10844] 쉬운 계단 수 (0) | 2023.04.14 |