백준 11054 - 가장 긴 바이토닉 부분 수열(골드 3)
문제
백준 11054 - 가장 긴 바이토닉 부분 수열
(https://www.acmicpc.net/problem/11054)
접근법
처음에는 LIS(가장 긴 부분 증가 수열)을 구하고, LIS가 끝나는 부분의 인덱스를 시작으로 LDS(가장 긴 부분 감소 수열)을 구하려고 했다.
그리고 실제로 예제도 통과했으나
알고보니 반례가 있었다.
1 5 4 2 3 같은 경우, 내 접근법대로 하면 답이 3이 나오지만 이 문제에서의 답은 4이다.
그래서 LIS를 구하는 범위를 하나하나 정해가면서 바이토닉 수열이 최대가 되는 값을 찾는 완전탐색 방식을 생각했다.
구현
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int n;
int arr[1001];
int dp[1001];
int ans=0;
int ansindex=0;
int lis(int limit)//LIS 찾는 함수
{
for(int i=1;i<=limit;i++)
{
dp[i]=1;
for(int j=1;j<=i;j++)
{
if(arr[i]>arr[j])
dp[i]=max(dp[i],dp[j]+1);
}
}
int ret=0;
for(int i=1;i<=limit;i++)
{
ret=max(ret,dp[i]);
}
return ret;
}
void lds(int limit,int ret) //LDS 찾는 함수
{
for(int i=limit;i<=n;i++)
{
dp[i]=ret;
for(int j=limit;j<=i;j++)
{
if(arr[i]<arr[j])
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
for(int i=1;i<=n;i++)//모든 경우 탐색
{
memset(dp,0,sizeof(dp));
int ret=lis(i);
lds(i,ret);
for(int j=1;j<=n;j++)
{
ans=max(dp[j],ans);
}
}
printf("%d",ans);
return 0;
}
Author And Source
이 문제에 관하여(백준 11054 - 가장 긴 바이토닉 부분 수열(골드 3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeongmin99/백준-11054-가장-긴-바이토닉-부분-수열골드-3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)