728x90
반응형
이 문제는 DP로 가장 긴 증가하는 부분 수열과 관련된 문제이다.
증가하다가 감소하는 수열, 증가하는 수열, 감소하는 수열 모두 바이토닉 수열에 해당된다.
순서대로 반복문을 돌다가 현 위치의 수 부터 이전 수를 비교했을 때 현 위치의 수가 큰 수일 경우 값을 올리는 방식으로
가장 긴 증가하는 수열의 길이를 구하고,
그리고 거꾸로 반복문을 돌리면서 현 위치 수 부터 가장 끝 수까지를 비교했을 때 현 위치의 수가 큰 수일 경우 값을 올리는 방식으로
가장 긴 증가하는 수열 거꾸로 버전의 길이을 구한다.
예를 들면,
1 2 3 4 5 4 3 2 1 이라는 수열이 있다면,
가장 긴 증가하는 수열 거꾸로 버전으로 생각해보면,
1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |
1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |
그리고 가장 긴 증가하는 수열로 생각해보면,
1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |
1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |
합했을 때 가장 큰 수 - 1을 해주면 가장 긴 바이토닉 부분 수열의 길이를 구할 수 있다.
-1을 해주는 이유는 수가 하나 겹치기 때문에 -1을 해준다.
// 가장 긴 바이토닉 부분 수열
#include <iostream>
using namespace std;
int main(void){
int count, answer = 1, arr[1001], dp[1001], rDp[1001];
cin >> count;
for(int i = 0; i < count; i++){
cin >> arr[i];
dp[i] = 1;
for(int j = 0; j < i; j++){
if(arr[i] > arr[j] && dp[i] <= dp[j]){
dp[i] = dp[j] + 1;
}
}
}
for(int i = count - 1; i >= 0; i--){
rDp[i] = 1;
for(int j = count - 1; j > i; j--){
if(arr[i] > arr[j] && rDp[i] <= rDp[j]){
rDp[i] = rDp[j] + 1;
}
}
}
for(int i = 0; i < count; i++){
answer = max(answer, dp[i] + rDp[i] - 1);
}
cout << answer;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 리모컨 (0) | 2020.11.04 |
---|---|
[algorithm] 백준 - 수 이어 쓰기 1 (0) | 2020.11.03 |
[algorithm] 백준 - 합분해 (0) | 2020.11.03 |
[algorithm] 백준 - 제곱수의 합 (0) | 2020.11.03 |
[algorithm] 백준 - 연속합 2 (0) | 2020.11.03 |