BOJ 6198 : 옥상 정원 꾸미기

문제링크

풀이요약

이분탐색 (LIS)

풀이상세

1. 빌딩을 볼 수 있는 최종 값은 지속적으로 감소하는 수열의 모든 경우의 수에서 자신을 제외한 갯수를 모두 더한 값이다.

2. 나의 경우 LIS를 응용하였다. 현재 자신이 가진 맨 뒤의 수보다 작다면 바로 백터에 집어넣고, 그게 아니라면 이분 탐색을 통해 현재 값과 같거나 작은 인덱스를 찾는다.

3. 해당 인덱스를 찾았다면, 그 인덱스보다 큰 범위는 모두 삭제하고, 현재의 값을 집어넣는다.

4. 전체 답에 현재의 백터 길이를 대입한다.

#include<iostream>
#include<vector>
using namespace std;
int N;
long long ans;
vector<int> v;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N;
    int num;
    cin >> num;
    v.push_back(num);
    for (int i = 1; i < N; i++) {
        cin >> num;
        if (v.back() <= num) {
            int l = 0;
            int r = v.size() - 1;
            while (l < r) {
                int mid = (l+r)/2;
                if(v[mid]<=num) r=mid;
                else l=mid+1;
            }
						if (!r) v.clear();
            v.assign(v.begin(), v.begin()+r);
        }
        v.push_back(num);
        ans += v.size() - 1;
    }
    cout << ans;
}