[백준 / #11054 / C++] 가장 긴 바이토닉 부분 순열

이번 문제는 DP 연습 겸 해서 풀어본 문제이다. 이 문제와 연관된 문제들도 풀어볼 예정이다.

 

https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

 

문제 해석:

 

 

문제는 LCS (Longest Common Sequence)와 비슷하고 다른 여타 순열 문제와 마찬가지로 동적 계획법(Dyanamic

 

Programming. 이하 DP)로 풀어나가는 문제이다. 문제에서 주어진 수열의 최대 길이는 1,000으로 비교적 작은 편에 속하므

 

로 모든 경우의 수를 탐색해도 1초 안에 충분히 들어오는 시간이기 때문에 dp테이블을 완성하고 최댓값을 찾는 과정에서

 

모든 경우를 탐색해도 충분한 시간이라고 본다. 이 문제에서 DP를 어떻게 사용하는 가는 아래에서 설명하겠다.

 

 

알고리즘 코드 및 해설:

 

 

 

DP 테이블을 어떻게 구성하느냐가 관건이다. 우선 문제에서 주어진 바이토닉 부분 순열은 오름차순으로 K에 도달하고 K

 

에서부터는 내림차순으로 구성되는 순열이라고 설명해주었다. 이는 곧 주어진 순열에서 K까지 갔을 때 구할 수 있는 최대

 

의 오름차순 부분 순열의 개수를 구해주고 K부터 순열의 끝까지 최대의 내림차순 부분 순열을 구해주고 더하면 된다. 한마

 

디로 주어진 순열에서 우선 오름차순으로 부분 순열의 최대 크기를 각각의 위치마다 구해주고 내림차순도 마찬가지로 구

 

해준 후 두 수를 각각의 위치에서 더했을 때 최대가 되는 K를 찾고 그 더한 값을 출력해주면 된다.

 

 

그렇다면 dp 테이블은 어떻게 구하냐, 바로 하나하나씩 대조해보면 된다. 이중 for문 중 첫번째 겉의 for문으로 순열에서 위

 

치를 지정하면 만약 그 위치보다 앞 쪽의 위치에 작은 수가 존재하면 그 수의 dp 값에 + 1 해주는 형식으로 구해주면 된다.

 

이 때, 주의해야 할 점은 이렇게 비교할 때 기존의 dp값을 같이 비교해줘야 한다는 것이다. 그리하여 최댓값을 dp에 남겨놓

 

으면 마찬가지로 그 뒤의 위치에서 순열 값을 비교하고 만약 비교하고자 하는 수보다 작으면 오름차순 / 혹은 역방향으로

 

내림차순이므로 dp값을 비교해주면 된다. 내림차순은 마찬가지로 끝에서부터 시작하여 역으로 비교해주며 dp 값을 채워

 

주면 된다. 

 

 

이번 문제는 그렇게 설명할 것이 많지 않아 여기서 마무리하겠다.

 

 

이렇게만 보면 참 쉬운데 필자는 DP 문제가 익숙치 않아 테이블을 구성하는 방법을 고안해내는데 오래 걸렸다. 앞에서 구

 

한 사례를 어떻게 이용할 지에 대해 생각만 잘해낸다면 쉽게 풀어낼 수 있을 것이다.