글 읽기 - 100%에서 틀렸다고 뜹니다.

wjb127 5년 전 0

벡터를 이용해서 LIS 구현을 nlogn의 시간 복잡도로 구현했는데 예외케이스가 무엇인지 모르겠습니다.

#include<iostream>
#include<algorithm>
#include<memory.h>
#include<vector>
using namespace std;

vector<long long int> semi;
vector<long long int>::iterator it;
long long int n;
long long int tmp;

int main()
{
    // cin가속
    cin.sync_with_stdio(false);
    
    // 개수 입력
    cin>>n;
    // 일단 semi에 저장
    semi.push_back(n);
    semi.reserve(n+1);
    
    // n개 입력받기
    for(long long int i=0;i<n;i++)
    {
        cin>>tmp;
        
        // 만약 현재 가장 큰 것보다 크면 (길이 늘리면서) 원소 추가
        if(semi.back() < tmp)
        {
            semi.push_back(tmp);
        }
        // 만약 현재 가장 큰 것보다 작다면
        else
        {
            // 벡터 탐색하면서
            for(it=semi.begin();it!=semi.end();it++)
            {
                // 더 작은 원소가 나타났을 때 그것 대신 저장하고 탐색 종료
                // 만약 이것이 맨 마지막 원소대신 저장되었다면 
                // 이 행위는 기존 벡터를 연장 가능하게 만드는 행위임
                if(*it > tmp)
                {
                    *it = tmp;
                    break;
                }
            }
        }
        
        
    }
    
    
    // 벡터 사이즈는 최장증가부분수열의 길이 이므로
    cout<<semi.size()<<"\n";
    
    
    return 0;
}

wjb127 5년 전 0

해결되었습니다

smucs13 4년 전 0

저거 reverse 어떤 용도로 쓰신거에요?

궁금해요 ㅠㅠ

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

문제

문제

출처

ICPC

100%에서 틀렸다고 뜹니다.

wjb127 5년 전 0

wjb127 5년 전 0

smucs13 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말