하루 쉬었다고 이렇게 머리가 리셋될 수 있나.. 이번주 코테인데....실력이 아찔하다..^^..
최소 스패닝 문제를 풀어봤다 며칠전에 풀었던 문제와 유사한데 차이점은 좀 특이하게 다른 문제들처럼 테스트케이스 개수가 나와있지 않고, 0 0 입력되면 종료 이런식으로 나와있었다. 게다가 테케 1이 테케 한 개만 입력되고 끝이라 아무생각없이 제출했더니 50%에서 오류가 났다.
0 0 이 나오면 리턴해주고, 0 0 이 나오기 전 까지 여러 번 테케를 받는다는 생각으로 구현해주면 해결 완료..
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int unf[200010];
struct State{
int v1,v2,dis;
State(int a, int b, int c){
v1 = a;
v2 = b;
dis = c;
}
bool operator<(const State &nn) const{
return dis<nn.dis;
}
};
int Find(int v){
if(v==unf[v]) return v;
else return unf[v] = Find(unf[v]);
}
void Union(int a, int b){
a = Find(a);
b = Find(b);
if(a!=b) unf[a] = b;
}
int n,m,x,y,z,org,sum;
int main(void){
while(1){
cin>>n>>m;
if(n==0 && m==0) return 0;
org = 0, sum = 0;
vector<State> vec;
for(int i=0; i<m; i++){
cin>>x>>y>>z;
vec.push_back(State(x,y,z));
org+=z;
}
for(int i=0; i<n; i++) unf[i] = i;
sort(vec.begin(),vec.end());
for(int i=0; i<vec.size(); i++){
int fa = Find(vec[i].v1);
int fb = Find(vec[i].v2);
if(fa!=fb){
Union(fa,fb);
sum+=vec[i].dis;
}
}
cout<<org-sum<<"\n";
}
return 0;
}
이분탐색으로 진행하고 찾은 값의 제곱근이 주어진 값과 같으면 출력 아니면 +1 해서 출력해주면 된다.
값 범위가 2^63라서 완탐했으면 무조건 시간초과 -> 이분탐색
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
using namespace std;
int main(void){
long long n;
cin>>n;
long long left = 0;
long long right = sqrt(n);
long long mid;
while(left<=right){
mid = (left+right)/2;
if(mid>=sqrt(n)) right = mid-1;
else left = mid+1;
}
if(mid*mid == n) cout<<mid<<"\n";
else cout<<mid+1<<"\n";
}
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
long long n,m;
vector<long long> vec;
cin>>n>>m;
for(long long i = 0; i<n; i++){
long long num;
cin>>num;
vec.push_back(num);
}
sort(vec.begin(),vec.end());
long long left = 0;
long long right = m * vec.back();
long long mid;
long long ans = right;
while(left<=right){
mid = (left+right)/2;
long long sum = 0;
for(int i=0; i<vec.size(); i++){
sum += (mid/vec[i]);
}
if(sum>=m){
ans = min(ans,mid);
right = mid-1;
}
else{
left = mid+1;
}
}
cout<<ans<<"\n";
}
주어진 별자리 조건을 보면 최소 스패닝임을 알 수 있다. (일직선으로 이은 형태 = 즉, 사이클이 없삼)
이 문제는 다른 문제와 달리 가중치가 주어져있지 않고, 두 별 사이의 거리만큼의 비용이 든다고 명시되어있다.
고로 직접 입력받은 별자리들 사이의 거리를 구해주어야 했다. 나는 cmath내에 pow, sqrt 함수를 사용했다.
입력된 거리 비용을 기준으로 오름차순 정렬한 뒤, 별자리를 이어주면 된다.
이때 혹시나 모든 별자리들 사이의 거리가 입력되어 벡터내에 여러 점이 중복으로 저장되어 있어서 문제가 생기지 않나? 라고 생각을 할 수도 있지만, 최소 스패닝 트리 알고리즘 특징은 이미 연결되어 있는지 체크를 해주기 때문에, 여러 점이 들어가도 문제가 없다..는...점..
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int unf[100],n;
struct State{
int v1,v2;
double dis;
State(int a, int b, double d){
v1 = a;
v2 = b;
dis = d;
}
bool operator<(const State &nn) const{
return dis<nn.dis;
}
};
int Find(int v){
if(v==unf[v]) return v;
else return unf[v] = Find(unf[v]);
}
void Union(int a, int b){
a = Find(a);
b = Find(b);
if(a!=b) unf[a] = b;
}
double a,b;
int main(void){
cin>>n;
for(int i=1; i<=n; i++) unf[i] = i;
vector<pair<double, double> > vec;
vector<State> v;
for(int i=0; i<n; i++){
cin>>a>>b;
vec.push_back(make_pair(a,b));
}
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
double x = pow((vec[j].first-vec[i].first),2);
double y = pow((vec[j].second-vec[i].second),2);
double dis = sqrt(x+y);
v.push_back(State(i,j,dis));
}
}
sort(v.begin(),v.end());
double ans = 0;
for(int i=0; i<v.size(); i++){
int fa = Find(v[i].v1);
int fb = Find(v[i].v2);
if(fa!=fb){
ans+=v[i].dis;
Union(fa,fb);
}
}
cout<<ans<<"\b";
}
이건 최소 스패닝 트리 - 크루스칼 알고리즘을 사용했다. 어쩌다 보니 오늘은 다 최단거리.. 문제네..
이 문제는 범위때문에 변수 선언에 고민을 좀 했는데.. 아슬아슬하거나 적은 것 보단 큰게 낫다 싶어서 long long 으로 선언했다.
일단 양방향이며/ 모든 건물이 연결되도록 최소한의 도로 = 최소 스패닝 트리 임을 확인할 수 있었다.
원하는 결과는 초기 비용 - 최소한의 도로 = 절약한 비용을 구해야 한다.
예외로 모든 건물을 연결하지 못할 때의 -1 출력도 고려해 주어야했다.
-> 이건 최소 스패닝 트리의 특징을 이용하면 쉽다. n개의 정점을 가진 최소 스패닝 트리는 간선의 연결 개수가 n-1개여야 모든 정점을 연결한 것이기 때문에, 연결 횟수가 n-1개가 아니라면 -1을 출력하도록 구현했다.
평소 스패닝 트리 구현 방법처럼 union- find 함수를 구현하고, 비용을 오름 차순으로 정렬해 최소의 비용으로 연결해주도록 구현했다.
그리고 초기에 구했던 초기 연결 비용에서 간선 연결 횟수가 n-1 인경우에 구한 합을 빼주며 결과를 도출했다.
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
long long unf[100001];
int n,m,a,b;
long long c,org;
struct State{
int v1,v2;
long long dis;
State(int a, int b, long long c){
v1 = a;
v2 = b;
dis = c;
}
bool operator<(const State &nn) const{
return dis<nn.dis;
}
};
long long Find(int v){
if(unf[v] == v) return v;
else return unf[v] = Find(unf[v]);
}
void Union(long long a, long long b){
a = Find(a);
b = Find(b);
if(a!=b) unf[a] = b;
}
int main(void){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i=1; i<=n; i++){
unf[i] = i;
}
vector<State> vec;
for(int i=0; i<m; i++){
cin>>a>>b>>c;
vec.push_back(State(a,b,c));
org+=c;
}
sort(vec.begin(),vec.end());
int cnt = 0;
long long sum = 0;
for(int i=0; i<m; i++){
long long fa = Find(vec[i].v1);
long long fb = Find(vec[i].v2);
if(fa!=fb){
sum += vec[i].dis;
cnt++;
Union(fa,fb);
}
}
if(cnt == n-1){
cout<<org-sum<<"\n";
}
else cout<<-1<<"\n";
}
