글 읽기 - 좀 특이하게 풀었는데 반례가 뭘까요

quantum 3년 전 0

뒤에서부터 읽으면서 lis 배열에 있는 값을 기준으로 사이값들을 채택해나가는 방식인데, 왜 틀린건지 궁금합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main(void)
{	
	FIO;
	int n, m;
	cin >> n;
	vector<int> v;
	vector<int> input(n);
	for(int i = 0; i < n; ++i) {
		cin >> m;
		input[i] = m;
		auto iter = lower_bound(v.begin(), v.end(), m);
		if (iter == v.end()) v.push_back(m);
		else *iter = m;
	}
	v.push_back(2000000000);
	int index = v.size() - 1;
	cout << index << '\n';
	vector<int> ans(index);
	for(int i = n - 1; i >= 0; --i) {
		if (input[i] < v[index] && input[i] >= v[index - 1]) ans[--index] = input[i];
	}
	for(int i = 0; i < v.size() - 1; ++i) {
		cout << ans[i] << ' ';
    }

	return 0;
}

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

문제

문제

출처

ICPC

좀 특이하게 풀었는데 반례가 뭘까요

quantum 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말