12015번 가장 긴 증가하는 부분 수열2(lower_bound, 이분탐색) - ☆

#문제링크 : www.acmicpc.net/problem/12015

<전략>

1. 블로그를 참고했습니다.

2. 벡터에 주어진 수열을 하나씩 담는다. 담는 조건은 v.back()보다 담으려는 수가 더 클 경우에 담는다.(증가수열)

3. 만약 담으려는 수가 v.back()보다 작거나 같다면, lower_bound 함수를 이용하여 v벡터에서 담으려는 수보다 크거나 같은 제일 작은 수의 위치를 구한다. 그리고 그 위치에 담으려는 수로 바꾸어준다.

4. 이것이 가능한 이유는, 2번의 경우에는 증가수열을 충족하므로 문제의 조건에 따라 당연히 담아야 한다. 3번의 경우, 담으려는 수가 v벡터 중 제일 큰 수보다 작거나 같다면 이 수가 들어갈 위치를 찾아 값을 바꾸어준다. 기존의 배열에 증가수열을 추가하는게 아닌, 단순히 값만 바꾸어주기때문에 증가수열의 길이에 영향을 주지 않는다. 즉, 증가수열의 길이만을 구하는 문제에서는 문제될게 없다는 뜻이다. 다만, 수열을 직접 구해야하는 경우에는 위와 같은 방법은 옳지 않다. 예를 들어보자.

2 3 5 4 8 6 7 1 배열이 있을때, 위와 같은 순서로 진행하면

[ 2 ] -> [ 2 3 ] -> [ 2 3 5 ] -> [ 2 3 4 ] -> [ 2 3 4 8 ] -> [ 2 3 4 6 ] -> [ 2 3 4 6 7 ] -> [ 1 3 4 6 7 ]

이 된다. 가장 긴 증가하는 수열은 [ 2 3 4 6 7 ] 인데도 불구하고 말이다. 이는 마지막 수 1이 2값을 덮어씌우기 때문에 문제가 생긴다. 따라서, 수열을 직접 구해야하는 경우에는 옳지 않은 방법이지만, 단순히 길이만을 구할 때는 유용하게 쓸 수 있는 방법이다.

5. 이분탐색인 이유는, lower_bound가 인덱스를 찾아갈때, 이분탐색을 사용하기 때문이다.

※주의사항

1. lower_bound의 반환값은 iterator 형이다. 이 값을 int형으로 변환시켜주는 방법은 해당 벡터의 v.begin()값을 빼주면 int형으로 정수값을 받을수가 있게 된다.

Code