백준 11053, 11054
1) 백준 11053 : 가장 긴 증가하는 부분수열 (https://www.acmicpc.net/problem/11053)
LIS문제. 이전에 풀어봤었어서 반가웠다.
참 볼때마다 대단하다고 느끼는 문제.
구하고자 하는 것은 수열의 크기이므로 이것에 집중한다.
LIS라는 벡터에 입력값들을 저장하는데 크기가 크면 이어 붙이면 되지만 더 작을 경우 생각을 해야 한다.
작을 경우에 이것을 선택할지 말지를 결정해야 하는데 그것을 벡터 내부에 삽입하는 것으로 대체한다.
이렇게 되면 이 수를 선택하는 경우도, 선택하지 않는 경우도 모두 따질 수 있기 때문이다.
예를들어 입력값에 따른 벡터내부의 변화를 봐보자.
6
10 20 10 30 20 50
라는 입력이 있을 때, 벡터는 순차적으로
(10) : {10}
(20) : 10 {20}
(10) : {10} 20
(30) : 10 20 {30}
(20) : 10 {20} 30
(50) : 10 20 30 {50}
이렇게 외어서 최종적으로 4개가 답이 된다.
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/6_11053.cpp
- 아래 문제랑 연계하기 위해서 좀 더 깔끔한 코드? 더 범용성 있는 코드? 는 이것
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/6_11053_2.cpp
2) 백준 11054 : 가장 긴 바이토닉 부분수열 (https://www.acmicpc.net/problem/11054)
LIS를 앞으로 한 번, 뒤로 한 번 돌려서 오르락 내리락 할 때 최대거리 찾는 문제.
두 개를 더할 때 중복 되므로 1을 빼줘서 답을 출력한다.
right의 경우 data를 거꾸로 순으로 해서 진행하면 된다.
그냥 store에서 O(n)으로 찾아도 되지만(? : 되는지는 안해봤네) 어짜피 store는 오름차순으로 정렬되어 있기 때문에 binary search사용하면 더 빠름 O(nlogn)
binary search로 구현된 lower_bound stl을 사용하면 편하다.
처음 해봤는데 편하더라구요. ㅎㄷ
data : 1 5 2 1 4 3 4 5 2 1
left : 1 2 2 1 3 3 4 5 2 1
right: 1 5 2 1 4 3 3 3 2 1
store는 계속 바뀌어서 의미 없음.
left/ right에 저장할 값들은 store의 사이즈이거나, lowerbound로 삽입된 것의 인덱스 이다.
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/6_11054.cpp
