글 읽기 - nlogn 방식 가장 긴 바이토닉 부분 수열 틀린 이유에 대해서 잘 모르겠습니다.

parkpeanut 1년 전 0

nlogn 방식으로 풀이한 내용인데,

49번째 라인에서

decreasebacktracking[i] = decreasebacktracking[location - decreasedp.begin()]; 와 같이 제출하면 틀렸다고 나오고

decreasebacktracking[i] = decreasedp.size();로 제출하면 맞았다고 나오는데요.

왜그런지 모르겠네요. 아무리 봐도 decreasebacktracking[i] = decreasebacktracking[location - decreasedp.begin()];이게 맞는거 같은데요..

다른 사이트에서 같은 바이토닉 수열 문제에선, 맞다고 나왔는데

여기서는 틀렸다고 나오네요.

이유를 알고 싶습니다.. 고수님들 도와주세요..ㅠㅠ

70%에서 틀렸다고 나옵니다.

#include <bits/stdc++.h>
using namespace std;

vector<int> increasedp;
vector<int> decreasedp;
vector<int> increasebacktracking;
vector<int> decreasebacktracking;
vector<int> b;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    for(int i = 0; i < N; ++i) {
        int n; cin >> n;
        b.emplace_back(n);
    }

    // 오름 차순
    increasebacktracking.resize(N, 1);
    for(int i = 0; i < N; ++i) {
        if(increasedp.empty()) {
            increasedp.emplace_back(b[i]);
            increasebacktracking[i] = increasedp.size();
        } else {
            if(increasedp.back() < b[i]) {
                increasedp.emplace_back(b[i]);
                increasebacktracking[i] = increasedp.size();
            } else {
                auto location = lower_bound(increasedp.begin(), increasedp.end(), b[i]);
                *location = b[i];
                increasebacktracking[i] = increasebacktracking[location - increasedp.begin()];
            }
        }
    }
    reverse(b.begin(), b.end());
    decreasebacktracking.resize(N, 1);
    for(int i = 0; i < N; ++i) {
        if(decreasedp.empty()) {
            decreasedp.emplace_back(b[i]);
            decreasebacktracking[i] = decreasedp.size();
        } else {
            if(decreasedp.back() < b[i]) {
                decreasedp.emplace_back(b[i]);
                decreasebacktracking[i] = decreasedp.size();
            } else {
                auto location = lower_bound(decreasedp.begin(), decreasedp.end(), b[i]);
                *location = b[i];
                decreasebacktracking[i] = decreasedp.size(); // decreasebacktracking[i] = decreasebacktracking[location - decreasedp.begin()];
                
            }
        }
    }
    reverse(decreasebacktracking.begin(), decreasebacktracking.end());
    int ans = 0;
    for(int i = 0; i < N; ++i) {
        ans = max(ans, decreasebacktracking[i] + increasebacktracking[i]);
    }
    cout << ans - 1;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

nlogn 방식 가장 긴 바이토닉 부분 수열 틀린 이유에 대해서 잘 모르겠습니다.

parkpeanut 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말