[BOJ] 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
예제 입력 1
10 1 5 2 1 4 3 4 5 2 1
예제 출력 1
7
이전 부분 수열 문제들을 조금만 바꿔 생각하면 되는 문제다. 원리는 같다.
코드
#include <iostream>
using namespace std;
int up[1001]={0,};
int down[1001]={0,};
int dp[1001] = {0,};
int arr[1001] = {0,};
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i];
up[1]=1;
for(int i=2;i<=n;i++){
up[i]=1;
for(int j=1;j<i;j++){
if(arr[i]>arr[j]){
up[i] = max(up[j]+1,up[i]);
}
}
}
down[n]=1;
for(int i=n-1;i>=1;i--){
down[i]=1;
for(int j=i+1;j<=n;j++){
if(arr[i]>arr[j]){
down[i] = max(down[j]+1,down[i]);
}
}
}
int max_dp=0;
for(int i=1;i<=n;i++){
dp[i]=up[i]+down[i]-1;
if(max_dp<dp[i]) max_dp=dp[i];
}
cout<<max_dp;
}
| cs |
up 배열은 첫번째 자리 부터 i 자리 까지의 증가하는 부분 수열의 최장 거리를 구해 저장한 배열이고, down 배열은 n 자리(마지막 자리)에서부터 거꾸로 증가하는 부분 수열의 최장 거리 (즉 i 에서 부터 n 까지 감소하는 부분 수열) 를 저장하는 배열이다.
dp 배열은 각 자리의 up과 down 값을 더하고 i 자리가 두번 더해지기 때문에 1을 뺀다. 그리고 max dp[i]값을 출력한다.
No comments: