너가 길면 얼마나 긴데?
문제
수열 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
문제 아이디어
- 문제에서 원하는 내용은 최장 증가 수열을 구하는 것인데,,, 이번에는 기존 최장 증가 수열 문제랑은 다르게 앞에서는 증가해야하고, 기준을 기점으로 감소해야 합니다. 기준을 기점으로 감소해야 한다는 뜻은 배열의 Reverse를 취했을 때 최장 증가 수열을 구하라는 말인거랑 똑같은겁니다
[1, 2, 5, 4, 3]이라고 했을 때 최장 증가 수열 중 하나는[1, 2, 3]이 될 것이고,- Reverse를 한
[3, 4, 5, 2, 1]에서 최장 증가 수열은[3, 4, 5]가 될 것입니다.
- 우리는 공통되는 최장 증가수열의 총 길이를 알아야 하기 때문에, 최장 증가 수열이 어떤게 있느냐? 가 아닌 **기준이 되는 인덱스까지 최장 증가 수열의 길이가 몇이나 되느냐?** 로 구하면 될 것입니다.
- 최장 증가 수열에 대해서 알고 싶으신 분은 저의 파이썬 알고리즘 블로그 LIS 포스팅을 참고하시면 됩니다!
[1, 2, 5, 4, 3]를 봤을 때, 각 인덱스 별 가질 수 있는 최장 길이는 다음과 같습니다.[1, 2, 3, 3, 3]
[3, 4, 5, 2, 1]를 봤을 때, 각 인덱스 별 가질 수 있는 최장 길이는 다음과 같습니다.[1, 2, 3, 3, 3]
- 위의 결과로 나온 배열을 더하면
[2, 4, 6, 6, 6]이 되고 MAX 값은 6이고, **공통되는 기준을 2번 카운트했기 때문에 1을 빼주면 답은 5**가 되는 겁니다. - 인덱스별 가질 수 있는 최장 길이가 이해가 되지 않는다면 위에서 태그한 제 파이썬 블로그를 참고하시면 될 겁니다.
문제 풀이
lowerBound함수는 최장 증가 수열에서 바꿔줘야할 인덱스를 찾는 함수입니다. 결과값으로 바뀔 인덱스 값을 리턴해줍니다. 값을 받아서 바꿔주기만 하면 됩니다.candVec는(idx, val)순서로 들어가게 되고, 값만을 저장하는게 아니라 인덱스를 저장하여 조금 더 쉽게lowerBound로 받은 값을 통해 바꾸면 됩니다.- 총 두 개의
for문을 통해서 앞에서 최장 증가 수열, 뒤에서 최장 증가 수열을 구해주는 것입니다. - 코드는 다음과 같습니다.
Code
C++
Python
오늘의 Tip!
- 기존에 주어지는 문제들은 최장 증가 수열의 길이를 구하라는게 전부이다. 최장 증가 수열을 구하라기에는 위상 정렬의 결과값 처럼 다양한 답이 나올 수 있기 때문이다. 이 문제에서는 기준이 되는 곳까지의 최장 증가 수열의 길이를 구해야하기 때문에 조금 응용해서 접근해야 한다.
- 다익스트라 문제도 그냥 일반 문제보다는, 경유지를 선택한다거나, 둘이 같이 출발해서 서로 다른 목적지로 간다거나 등의 문제도 동일 선상에 있다.
- 문제를 보고 LIS 같지만, 아이디어가 떠오르지 않는 사람들은 일단 구현해보고 결과값을 통해서 유추하는 것도 나쁜 방법은 아니다. (그러다가 어떻게 얻어 걸리기도 하기 때문?)