글 읽기 - 반례부탁드립니다...

seonh4996 4년 전 0

글에 있는 반례 대입해봐도 다 되는데 어디가 틀린지 모르겠습니다. ㅜ

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int dp[1'000'001] ={0,};

int main(){
	
	vector<int> v;
	
	int N;
	cin >> N;
	
	for(int i = 0; i < N; i++){
		int a;
		cin >> a;
		v.push_back(a);
	}
	
	vector<int> temp;
	vector<int> temp_idx;
	temp.push_back(-987654321);
	temp_idx.push_back(-1);
	for(int i = 0; i < v.size(); i++){
		
		auto idx = lower_bound(temp.begin(),temp.end(),v[i]);
		
		if(idx == temp.end()){
			dp[i] = temp_idx.back();
			temp.push_back(v[i]);
			temp_idx.push_back(i);
		}
		else{
			dp[i] = dp[temp_idx[idx-temp.begin()]];
			*idx = v[i];
			temp_idx[idx-temp.begin()] = i;
		}
		
	}
	
	vector<int> ans;
	ans.push_back(temp.back());
	int start = dp[temp_idx.back()];
	
	while(start != -1){
		ans.push_back(v[start]);
		start = dp[start];
	}
	reverse(ans.begin(),ans.end());
	
	cout << temp.size()-1 << '\n';
	
	for(auto it = ans.begin(); it != ans.end(); it++){
		cout << *it << " ";
	}
	
}

seonh4996 4년 전 0

해결했네요..

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int dp[1'000'001] ={0,};

int main(){
	
	vector<int> v;
	
	int N;
	cin >> N;
	
	for(int i = 0; i < N; i++){
		int a;
		cin >> a;
		v.push_back(a);
	}
	
	vector<int> temp;
	vector<int> temp_idx;
	temp.push_back(-987654321);
	temp_idx.push_back(-1);
	for(int i = 0; i < v.size(); i++){
		
		auto idx = lower_bound(temp.begin(),temp.end(),v[i]);
		
		if(idx == temp.end()){
			dp[i] = temp_idx.back();
			temp.push_back(v[i]);
			temp_idx.push_back(i);
		}
		else{
			dp[i] = temp_idx[idx-temp.begin()-1]; //잘못생각했네요.. 
			*idx = v[i];
			temp_idx[idx-temp.begin()] = i;
		}
		
	}
	
	vector<int> ans;
	ans.push_back(temp.back());
	int start = dp[temp_idx.back()];
	
	while(start != -1){
		ans.push_back(v[start]);
		start = dp[start];
	}
	reverse(ans.begin(),ans.end());
	
	cout << temp.size()-1 << '\n';
	
	for(auto it = ans.begin(); it != ans.end(); it++){
		cout << *it << " ";
	}
	
}

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

문제

문제

출처

ICPC

반례부탁드립니다...

seonh4996 4년 전 0

seonh4996 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말