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

4주차에 잠수를 탄 박성훈이라고 합니다 ㅠㅠ

요 몇주간 진짜 바빴어서 이것저것 잡다한 이유로

4주차는 건너뛰게 된것 같아요

그래도 백준은 그 사이에 계속 풀긴 했었습니다 ㅠㅠ

색이 연해졌지만 일단 칠해져있기는한 관계로

4주차 것까지 합쳐서 2주치 분량의 백준 문제 요약을 해보려고 합니다.

 

#1 백준 1561 - 놀이 공원 ( G2 )

https://blog.koderpark.dev/380

백준 BOJ 1561 - 놀이 공원

이분 탐색을 사용해서 사람 N명이 탑승하는데 걸리는 최소의 시간을 구해준 다음,

이 시간을 T라고 하면 T-1 시점에서는 사람들이 다 탑승하지 못했을 것이므로,

T-1 시점에서 한명씩 태워보면서

태워서 딱 N명이 되는 경우를 찾으면 되는 문제였다.

 

이분 탐색의 최대 범위는 600억쯤 되니 long long 으로 잡아줘야 한다.

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

ll arr[12345] = {0};
ll N,M;

ll search(ll s, ll e){
	ll mid = (s+e)/2;
	
	if(s==e) return mid;
	
	ll cnt = M;
	for(int i=0; i<M; i++) cnt += mid/arr[i];
	
	if(cnt >= N) return search(s,mid);
	else return search(mid+1,e);
}

int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++){
		cin >> arr[i];
	}
	
	if(N <= M){
		cout << N;
		return 0;
	} 
	
	ll ret = search(1, 60000000000LL);
	ll cnt = M;
	
	for(int i=0; i<M; i++) cnt += (ret-1)/arr[i];
	for(int i=0; i<M; i++){
		if(ret % arr[i] == 0) cnt++;
		if(cnt == N){
			cout << i+1;
			return 0;
		}
	}
}

 

#2 백준 15661 - 링크와 스타트 ( S1 )

https://blog.koderpark.dev/382

백준 BOJ 15661 - 링크와 스타트

비트마스킹을 통해서 팀을 구분해준다.

비트가 켜진 경우 A팀, 비트가 꺼진 경우 B 팀으로 각 팀을 나눠준 다음,

사람 두명을 O(N^2) 로 골라서 같은 팀에 있는 경우 능력치 계산을 해주면 된다.

 

전체 시간복잡도는 O(2^N * N^2) 인데,

상당히 아슬아슬한 속도로 정답을 받았던 걸로 기억한다.

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

int S[50][50] = {0};

int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			cin >> S[i][j];
		}
	}
	
	int ans = 998244353;
	for(int K=0; K<(1<<N); K++){
		
		int A = 0;
		int B = 0;
		
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				if(K & (1<<i) && K & (1<<j)){
					A += S[i][j];
				}
				
				if(!(K & (1<<i)) && !(K & (1<<j))){
					B += S[i][j];
				}
			}
		}
		
		ans = min(abs(A-B), ans);
	}
	
	cout << ans;
	return 0;
}

 

#3 백준 13975 - 파일 합치기 3 ( G4 )

https://blog.koderpark.dev/385

백준 BOJ 13975 - 파일 합치기 3

파일 임시파일 구분 없이 우선순위 큐에 넣어서 관리하면서,

가장 비용이 작은 파일 두개를 합쳐서 새로운 파일으로 큐에 넣어주면 된다.

 

전체 시간복잡도는 O(KlogK)

PQ의 우선순위를 정 반대로 바꿔 최솟값을 꺼내주기 위해서 greater<ll> 을 사용해줬다.

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

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int T;
	cin >> T;
	while(T--){
		priority_queue<ll, vector<ll>, greater<ll>> pq;
		ll N,K;
		ll ans = 0;
		
		cin >> N;
		for(int i=0; i<N; i++){
			cin >> K;
			pq.push(K);
		}
		
		while(pq.size() > 1){
			ll a = pq.top(); pq.pop();
			ll b = pq.top(); pq.pop();
			
			ans += a+b;
			pq.push(a+b);
		}
		
		cout << ans << "\n";
	}
	return 0;
}

 

#4 백준 2473 - 세 용액 ( G3 )

https://blog.koderpark.dev/386

백준 BOJ 2473 - 세 용액

한국정보올림피아드 기출문제.

세 수를 O(N^3) 으로 고르면 시간초과를 받으므로

O(N^2logN) 으로 고를 수 있도록 알고리즘을 짰다.

O(N^2) 로 두개의 수를 골라서 원소의 갯수가 N^2개인 그 합 배열 SUM 을 만들어 줬고,

해당 SUM 배열을 순회하면서 이분탐색으로 셋의 합이 0이 되도록 하는 수를 찾아주면 된다.

 

합이 0이 되는 수를 찾기 위해서는 SUM의 원소 K에 대해서

-K 에 가장 가까운 수를 이분탐색으로 구해주면 된다.

 

배열 인덱스 바깥으로 벗어나지 않게 처리를 잘 해줘야 한다.

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

vector<ll> arr;

int main(){
	int N,tmp;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> tmp;
		arr.push_back(tmp);
	}
	
	sort(arr.begin(), arr.end());
	
	ll ans = 1e18;
	ll ret[3] = {0};
	
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			auto k = lower_bound(arr.begin(), arr.end(), (arr[i]+arr[j])*-1) - arr.begin();
					
			if(k>0){
				if(i!=k-1 && j!=k-1 && ans>abs(arr[k-1]+arr[i]+arr[j])){
					ans = abs(arr[k-1]+arr[i]+arr[j]);
					ret[0] = i;
					ret[1] = j;
					ret[2] = k-1;
				}
			}
			if(k<N){
				if(i!=k && j!=k && ans>abs(arr[k]+arr[i]+arr[j])){
					ans = abs(arr[k]+arr[i]+arr[j]);
					ret[0] = i;
					ret[1] = j;
					ret[2] = k;
				}
			}
		}
	}

	sort(ret, ret+3);
	for(int i=0; i<3; i++) cout << arr[ret[i]] << " ";
	return 0;
}

 

#4 백준 14719 - 빗물 ( G5 )

https://blog.koderpark.dev/387

백준 BOJ 14719 - 빗물

어느 한 위치 i에서 고이게 되는 빗물의 양은

그 위치의 왼쪽 [0,i) 구간에서 가장 높은 블록 높이와

그 위치의 오른쪽 (i,N) 구간에서 가장 높은 블록 높이 중

더 작은 값을 따른다.

 

왼쪽 높이를 l, 오른쪽을 r이라 했을때

식으로 계산하면 min(l,r) - i 가 되는데,

물이 고일수 없는 경우 음수 만큼의 물이 고이는것을 막기 위해서

l과 r은 처음에 높이 i로 초기화 되어야 한다.

 

전체 시간복잡도는 O(N^2)

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

int N,M;
int arr[1234] = {0};

int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++) cin >> arr[i];
	
	int ans = 0;
	for(int i=0; i<M; i++){
		int l = arr[i];
		int r = arr[i];
		
		for(int j=0; j<M; j++){
			if(j<i){
				l = max(l, arr[j]);
			}
			if(i<j){
				r = max(r,arr[j]);
			}
		}
		
		//printf("[%d]", min(l,r)-arr[i]);
		
		ans += min(l,r)-arr[i];
	}
	cout << ans;
}

 

#5 백준 1613 - 역사 ( G3 )

https://blog.koderpark.dev/390

백준 BOJ 1613 - 역사

플로이드 와셜의 필요성을 재확인한 문제.

입력으로 들어오는 사건들을 그래프로 봐서

 

arr[a][b]를 a가 b 앞에 있는지를 체크하는 용도로 사용한다.

대략 단방향 그래프를 구성한다고 이해해도 될 듯 하다.

 

플로이드 와셜로 모든 a,b 쌍에 대해서 계산해주면 정답을 받아낼 수 있다.

 

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

bool arr[456][456] = {0};

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N,K;
	int a,b;
	cin >> N >> K;
	for(int i=0; i<K; i++){
		cin >> a >> b;
		arr[a][b] = true;
	}	
	
	for(int k=1; k<=N; k++){
		for(int i=1; i<=N; i++){
			for(int j=1; j<=N; j++){
				if(arr[i][k] && arr[k][j]) arr[i][j] = true;
			}
		}
	}
	
	int Q;
	cin >> Q;
	while(Q--){
		cin >> a >> b;
		if(arr[a][b]) 		cout << "-1\n";
		else if(arr[b][a]) 	cout << "1\n";
		else 				cout << "0\n";
	}
	return 0;
}

 

첨언

요즘 이것저것 일이 많아서 일에 치여사는중...

다시 카페인 공장이 돌아가니까

영 낮에도 피곤하다 ㅠㅠ