알고리즘 2인 스터디 #6주차 - 박성훈

슬슬 무감각해져가는 백준 풀이

긴말없이 바로 시작합니다.

 

#1 백준 10216 Count Circle Groups ( G4 )

https://www.acmicpc.net/problem/10216

10216번: Count Circle Groups

유니온-파인드 알고리즘을 사용합니다.

입력받은 모든 점들에 대해서 직선거리를 계산해주고

반지름 두개의 합보다 짧다면 같은 그룹으로 joint 합니다.

이 과정에 O(N^2) 를 사용하고

 

O(N)으로 순회해주면서

그룹의 갯수를 세서 출력해주면 됩니다.

 

함수 conn은 두 범위가 서로 겹치는지 T/F를 반환합니다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

pair<int,int> pos[3456];
int dis[3456] = {0};

int parent[3456] = {0};
set<int> s;

bool conn(int i, int j){
	int x = pos[i].x - pos[j].x;
	int y = pos[i].y - pos[j].y;
	
	//printf("[%d %d - %d]", i, j, x*x + y*y);
	
	if(x*x + y*y <= (dis[i]+dis[j]) * (dis[i]+dis[j])){
		return true;
	}
	return false;
}

int find(int k){
	if(parent[k] == k) return k;
	return parent[k] = find(parent[k]);
}

void joint(int a, int b){
	a = find(a);
	b = find(b);
	if(a!=b) parent[a] = b;
	return;
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int T;
	cin >> T;
	while(T--){
		for(int i=0; i<3456; i++) parent[i] = i;
		s.clear();
		
		int N;
		cin >> N;
		for(int i=0; i<N; i++){
			cin >> pos[i].x >> pos[i].y >> dis[i];
		}
		
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				if(conn(i,j)){
					joint(i,j);
				}
			}
		}
		
		for(int i=0; i<N; i++){ s.insert(find(i)); }
		cout << s.size() << "\n";
	}	
	return 0;
}

 

#2 백준 2877 4와 7 ( G5 )

https://www.acmicpc.net/problem/2877

2877번: 4와 7

4와 7이라는 두 숫자 간에 우열 관계가 명확하기 때문에,

0과 1으로 봐도 대소비교에 있어서 아무런 문제가 없다.

이를 변형해서 생각해보면

1 - 0

2 - 1

3 - 00

4 - 01

5 - 10

6 - 11

7 - 000 에 매칭되는데,

이 각각의 0과 1로된 문자열들의 앞에 1을 하나만 붙여보면

연속해서 증가하는 이진수임을 찾아볼 수 있다.

 

10(2) < 11(3) < 100(4) < 101(5) ....

이러한 이진수들은 입력으로 들어오는 K보다 1 큰 수인데,

따라서 K에 1을 더하고 이를 이진수로 변환한다음

제일 앞자리를 떼서 출력해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

stack<bool> s;

int main(){
	int N;
	cin >> N;
	N++;
	
	while(N){
		s.push(N%2);
		N/=2;
	}
	
	s.pop();
	while(!s.empty()){
		if(s.top()){
			cout << "7";
		}
		else cout << "4";
		s.pop();
	}
	return 0;
}

백트래킹 풀이가 정해인듯한데

이진수 아이디어로 좀 더 깔끔하게 풀어낼 수 있고,

깔끔하게 풀어내서 마음에 드는 문제.

 

#3 백준 12886 돌 그룹 ( G4 )

https://www.acmicpc.net/problem/12886

12886번: 돌 그룹

BFS 문제이다.

세 변수 A,B,C를 모두 관리하면서 탐색을 해주면,

방문 체크를 하는 배열의 크기가 과도하게 커져서 정답을 받을 수 없다.

A,B,C 셋의 합이 일정함을 이용해서 변수 하나를 떼고,

두개의 변수 A,B만 관리하면서 탐색해주면 된다.

 

이때 셋의 합이 3의 배수가 아니라면

아무리 변형해도 돌을 같은 개수로 통일시킬 수 없으므로 바로 0을 출력하고

프로그램을 종료해주면 된다.

 

메모리 아낄 생각이니 뭐니 이것저것 귀찮았던 문제.

#include <bits/stdc++.h>
using namespace std;

bool vis[1501][1501] = {0};
queue<pair<int,int>> q;

int main(){
	int A,B,C;
	int sum;
	bool flag = false;
	
	cin >> A >> B >> C;
	
	sum = A+B+C;
	q.push({A,B});
	
	if(sum%3 != 0){ cout << 0; return 0; }
	
	while(!q.empty()){
		int a = q.front().first;
		int b = q.front().second;
		int c = sum-a-b;
		q.pop();
		
		if(vis[a][b]) continue;
		vis[a][b] = true;
		
		if(a == b && b == c){
			flag = true;
			break;
		}
		
		if(a<b) q.push({a+a,b-a});
		if(a<c) q.push({a+a,b});
		if(b<a) q.push({a-b,b+b});
		if(b<c) q.push({a,b+b});
		if(c<a) q.push({a-c,b});
		if(c<b) q.push({a,b-c});
	}
	
	cout << flag;
	return 0;
}