[BOJ12015] 가장 긴 증가하는 부분 수열 2

1. 문제

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

2. Note

풀 수 없어서 검색하여 풀었다. 자주 쓰인다는 알고리즘이라니 잘 알아두자. (비슷한 문제 찾아보기)

2.1. 핵심 아이디어

L[i] = 길이 i인 증가하는 부분 수열을 만들 수 있는 마지막 원소 중 가장 작은 값 (L은 1-based)
https://seungkwan.tistory.com/8

2.2. vector::back()

벡터의 마지막 원소를 반환한다. 간편하게 쓸 수 있어서 좋다.

2.3. 다른 풀이

세그먼트 트리로도 풀 수 있다고 한다. 세그먼트 트리를 공부한 뒤 다시 풀어보자.

3. Reference

• https://seungkwan.tistory.com/8