백준 4198 열차정렬

너무 어렵당 …

n번째를 기준으로 lis와 lds를 구해서 해결할 수 있다.

dp로도 해결 가능하지만 이분탐색을 사용해서도 해결할 수 있다.

근데 dp도 어려운데 😞

dp로 풀기

문제를 잘 보면 결국 n번째 수를 기준으로 lis와 lds를 구하는 것이다. 따라서 cache를 기존에 구하던 거랑은 다르게 설정해야하는데

cacheLis[idx] = idx를 시작으로 하는 lis 
cacheLds[idx] = idx를 시작으로 하는 lds

그 이유는 다음의 예시로 알 수 있다. {4, 1, 2, 3} 에서 4를 기준으로 기존의 메모이제이션 방식으로 하면 4를 끝으로 하는 lis와 lds를 구하기 때문에 결국 1 + 1 - 1 = 0이 된다.

코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin>>N;
    vector<int> arr(N);
    vector<int> lis(N, 0), lds(N, 0);
    for (auto &a:arr) {
        cin >> a;
    }
    for(int i=N-1; i>=0; --i) {
        lis[i] = lds[i] = 1;
        for(int j=i+1; j<N; ++j) {
            if(arr[i] > arr[j])
                lds[i] = max(lds[i], lds[j] + 1);
            if(arr[i] < arr[j])
                lis[i] = max(lis[i], lis[j] + 1);
        }
    }
    int ret = 0;
    for(int i=0; i<N; ++i) {
        ret = max(ret, lis[i] + lds[i] - 1);
    }
    cout<< ret;
    //std::cout << "Hello, World!" << std::endl;
    return 0;
}

이분탐색으로 풀기

Written by@[jungin]

안녕하세요

GitHub