2021년 1월 16일 PS 일지

1일 3BOJ

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

해싱 연습문제

내가 즐겨쓰는 소수들: 5e5+9, 5e5+29, 1e9+7, 1e9+9, 1e9+21

1e9+21은 잘 알려져 있지 않은 소수이기 때문에 저격을 피할 수 있어 좋다.

머,,, 대부분 저격해놨다면 랜덤을 쓰자.

 

정렬하면 쉽게 풀 수 있겠지만 일부러 해싱을 써 봤다.

생각나는 또 다른 풀이로는 정렬한 다음 투포인터를 써서 비교 과정을 O(n)으로 구현할 수 있겠다.

이런식으로 L, R을 옮겨가면 된다.

 

파이썬보다 시간이 오래 걸리는 기적을 경험했다 ㅋㅋㅋㅋㅋ

 

www.acmicpc.net/problem/15318

15318번: 새로운 수열

머리로만 문제 풀기에 간단한 풀이를 적었다

 

www.acmicpc.net/problem/2188

2188번: 축사 배정

이분매칭?

모르는거다! 하고 다른 블로그를 봤다.

대표예제: 열혈강호 -> 클릭.

엥, 풀려있네?

공부한 기억이 없는데 증거는 남아있는 신기한 경험을 했다.

 

이분매칭에 관해 간단한 언급을 하자면

dfs로 구현할 때 더 빠르게 하는 방법이 존재한다.

일반적으로는 visit 배열을 소스(매칭의 시작점)에 대해 설정하고

dfs를 돌리는데,

나는 싱크에 설정해서 했더라.

+ 싱크 중에서 아직 연결되지 않은 것이 있다면 그곳에 우선적으로 연결한다.

그렇게 하니까 시간이 훨씬 빠름.

 

나중에 공부할 목적으로 열혈강호의 내 코드를 첨부한다.

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
const int INF = 1e9;
using namespace std;
int n,m,team[1001],vis[1001];
vector<int> v[1001];
inline int R(int x=0){
	return scanf("%d",&x),x;
} 
int viscount = 0;
bool dfs(int k){
	for(int next:v[k]){
		if(vis[next]!=viscount && !team[next]){
			vis[next]=viscount;
			team[next]=k;
			return 1;
		}
	}
	for(int next:v[k]){
		if(vis[next]!=viscount){
			vis[next]=viscount;
			if(dfs(team[next])){
				team[next]=k;
				return 1;
			}
		}
	}
	return 0;
}
int main(){
	n=R(); m=R();
	for(int i=1,c,k;i<=n;i++){
		c=R();
		while(c--){
			k=R();
			v[i].push_back(k);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
        ++viscount;
		if(dfs(i)) ans++;
	}
	printf("%d",ans);
}

UPD) 문제 풀어보니까, 테스트케이스에 따라 케바케다. 그냥 더 편한 구현으로 하자.