[BOJ] 14003 가장 긴 증가하는 부분 수열 5

14003번: 가장 긴 증가하는 부분 수열 5

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

---

어제와 같은 문제였다. 지나가는데 플레 문제지만 너무 풀 수 있을 것 같아서 도전했다. 어제 비슷한 문제를 풀어서 실제로도 쉽게 풀 수 있었다.

 

어제 문제랑 다른 점이 있다면 어제는 LIS에 속하지 않는 원소들을 찾았지만 오늘은 그냥 LIS를 찾으면 되는 문제였다. LIS의 길이를 찾은 이후에 벡터에 들어있는 값들은 LIS와 관련이 없기 때문에 추가적인 정보가 필요하다. 예시는 바로 답이 나오지만 그냥 제출하면 어림도 없다.

 

그래서 어제랑 비슷한 과정을 거친다. 대신 어제랑은 반대로 하면 된다. 그리고 마지막엔 거꾸로 출력하면 답을 얻을 수 있다.

 

벡터가 많이 쓰여서 시간이 시간을 더 단축할 수 있을 것 같긴 하다. lower_bound 함수도 배열에서  작동하는 것으로 알고 있다. 그런데 크기 잡아놓는 게 귀찮아서 일단 벡터로 풀었다. 그래도 궁금해서 배열로 바꿔봤는데 216ms에서 204ms 정도밖에 개선되지 않았다. 최대 크기가 100만 정도라서 효과가 있을 줄 알았는데 크게 없었다. push_back도 어디서 보기로는 O(1)이라고 봤던 것 같은데 진짜인가 보다.

 

벡터를 사용한 코드

 

 

배열을 사용한 코드

 

 

후기)

확실히 많이 풀면 당장은 쉬워지긴 한다. 그런데 한 달만 지나도 기억이 안 난다...

내일 개강이다. 비대면이라서 그런가 별로 와닿지도 않는다. 그래도 이번 학기엔 대면 강의가 하나는 있다.