글 읽기 - 간단한 LIS의 길이와 LIS의 구성요소 찾는 문제인데 제출하자마자 틀리네요ㅠ

goodinet 7년 전 0

ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ코드를 몇 번이나 살펴보고 계속 다르게 제출해도 틀렸다 나오네요ㅜㅜ

N이 0일 때는 문제 조건에서 조차 안들어가고, 출력을 맨 뒤에 띄어쓰기 안하게 해도 안되고 어떻게 해도 안되네요

대체 무엇이 문제인 걸까요ㅠㅠㅠ 부탁드립니다.

#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

vector<int> lis;
vector<int> v(1001);
vector<int> path(1001,-1);

int main(){
  int N;
  scanf("%d",&N);
  for(int i=0;i<N;i++)
    scanf("%d",&v[i]);

  lis.push_back(v[0]);
  for(int i=1;i<N;i++){
    if(lis.back()<v[i]){
      path[v[i]]=lis.back();
      lis.push_back(v[i]);
    }
    else{
      auto it = lower_bound(lis.begin(),lis.end(),v[i]);
      *it = v[i];
      if(it!=lis.begin())
        path[v[i]]=*(--it);
    }
  }
  printf("%lu\n",lis.size());

  stack<int> s;
  int x = lis.back();
  while(x != -1){
    s.push(x);
    x=path[x];
  }
  while(!s.empty()){
    printf(" %d",s.top());
    s.pop();
  }
  printf("\n");
}

goodinet 7년 전 0

(작성자) 딴 코드를 찾아서 제출해봤는데 맞는데ㅠㅠㅠㅠㅠㅠ이건 왜 틀렸는 지 이해가 안되네요..ㅜㅜㅜㅜㅜㅜㅜ

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

문제

문제

출처

ICPC

간단한 LIS의 길이와 LIS의 구성요소 찾는 문제인데 제출하자마자 틀리네요ㅠ

goodinet 7년 전 0

goodinet 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말