[C++][BOJ 2170 선긋기]

BOJ 2170 선긋기

 

 

 

[실패 소스코드]

배열을 만들어 해당 구간 방문시 TRUE TREU인 곳에만 길이 구하기  

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll len = 2000000010, bias = 1000000000; //2000000010  1000000000
	bool line[len]={0,};
	int n;
	ll answer=0;
	cin >> n;
	for(int i=0;i<4;i++){
		ll s,e;
		cin>>s>>e;
		for(ll j = s ; j<e;j++){
			if(!line[j+bias]){
				answer++;
				line[j+bias]=true;
			}
		}
		
	}
	cout<<answer;
	
}

문제의 192MB로 메모리 제한이 있다.

지금 풀이의 배열만 1byte * 2,000,000,000 = 20MB정도한다.

 

정렬문제인데 이렇게 풀었다. seg fault 나왔다. 범위가 작다면 이 방법으로도 가능할 것 같다.

 

 

 

[성공한 소스 코드]

정렬해서 조건 맞춰서 구하기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,answer=0;
	cin >> n;
	vector<pair<int,int>> v;
	for(int i = 0 ; i < n ; i++){
		int s,e;
		cin >>s>>e;
		v.push_back({s,e});		
	}
	sort(v.begin(),v.end());
	
	int s = v[0].first, e=v[0].second;
	for(int i = 1 ; i < n ; i++){
		int from= v[i].first,to=v[i].second;
		if(from <= e){ // start 기준 정렬했으니까 이것만 검사  
			e = (to > e)? to : e;   //조건 조심
		}
		else{//안겹치는 경우 
			answer+= (e-s);
			s=from;
			e=to;
		}		
	}
	answer+= (e-s);
	cout<<answer;
}