3/23 ~ 3/30 PS 기록

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

33725 그리디 알고리즘

가장 체력이 큰 몬스터 부터 거꾸로 시작하는 로직

#include <bits/stdc++.h>
#define MAX 500001
#define int long long
using namespace std;

int A[MAX], B[MAX], dp[MAX], sum[MAX];

int32_t main() {

    int N, ans, mx = -1, s;

    cin >> N;

    for(int i = 0; i < N; i++) {
        cin >> A[i];
        if(mx < A[i]) {
            mx = A[i];
            s = i;
        }
    }
    for(int i = 0; i < N; i++) {
        cin >> B[i];
    }

    int curr = mx;
    ans = mx;

    for(int i = 1; i < N; i++) {
        int j;
        j = (s - i + N) % N;
        curr = max(A[j], curr-B[j]);
        ans = min(ans, curr);
    }
    cout << ans;
}

 

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

1715 우선순위 큐, 그리디

작은 거부터 합치면 비용이 준다.

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

int main() {
	int N, ans = 0;
	cin >> N;
	priority_queue<int, vector<int>, greater<int>> pq;
	for(int i = 0; i < N; i++) {
		int x;
		cin >> x;
		pq.push(x);
	}
	while(!pq.empty()) {
		if(pq.size() == 1) {
			break;
		}
		int a, b, c;
		a = pq.top();
		pq.pop();
		b = pq.top();
		pq.pop();
		c = a+b;
		ans += (c);
		pq.push(c);
	}
	cout << ans;
}

 

 

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

17612 

문제에서 시키는 대로 구현하면 된다.

나갈 때는 번호가 큰 순서대로

들어올 때는 번호가 작은 순서대로.

cmp 정렬과 우선순위 큐를 이용하여 간단히 구현.

#include <bits/stdc++.h>
#define int long long
using namespace std;
using pp = array<int, 2>;
using ppp = array<int, 3>;
bool cmp(ppp a, ppp b) {
	if(a[0] == b[0])
		return a[1] >= b[1];
	return a[0] < b[0];
}

int32_t main() {
	int N, K, sum = 0;
	cin >> N >> K;
	priority_queue<pp, vector<pp>, greater<pp>> pq;
	vector<ppp> ans;
	for(int i = 1; i <= K; i++) {
		pq.push({0, i});
	}
	for(int i = 0; i < N; i++) {
		int id, w, c, n;
		c = pq.top()[0];
		n = pq.top()[1];
		pq.pop();
		cin >> id >> w;
		pq.push({w + c, n});
		ans.push_back({w+c, n, id});
	}
	sort(ans.begin(), ans.end(), cmp);
	
	for(int i = 0; i < N; i++) {
		int id = ans[i][2];
		sum += (i+1)*id;
	}
	cout << sum;
}

 

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

13904 우선순위 큐, 그리디

과제 마감일순으로 정렬 후

현재 처리할 수 있는 최장 마감일 보다 과제 수가 더 많으면

가장 가치가 작은 과제를 드랍. (은근 합리적이다?)

#include <bits/stdc++.h>
using namespace std;
using p = array<int,2>;
int main() {
	
	int N, ans = 0;
	priority_queue<p, vector<p>, greater<p>> pq;
	cin >> N;
	vector<p> v;
	for(int i = 0; i < N; i++) {
		int d, w;
		cin >> d >> w;
		v.push_back({d, w});
	}
	sort(v.begin(), v.end());
	for(int i = 0; i < N; i++) {
		pq.push({v[i][1], v[i][0]});
		while(pq.size() > v[i][0]) {
			pq.pop();
		}
	}
	while(!pq.empty()) {
		ans += pq.top()[0];
		pq.pop();
	}
	cout << ans;
}

 

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

32414 다익스트라

멀티소스 다익스트라라는 신기한 개념을 처음 배웠다.

+ 어려운 로직

#include <bits/stdc++.h>
#define int long long
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using p = array<int,2>;
int32_t main() {
	fastio
	int N, M;
	cin >> N >> M;
	vector<int> dist(N+1), t(N+1);
	vector<vector<p>> connected(N+1);
	
	for(int i = 1; i <= N; i++) {
		cin >> t[i];
	}
	
	for(int i = 0; i < M; i++) {
		int x, y, d;
		cin >> x >> y >> d;
		connected[x].push_back({y, d});
		connected[y].push_back({x, d});
	}
	priority_queue<p, vector<p>, greater<p>> pq;
	
	for(int i = 1; i <= N; i++) {	
		pq.push({t[i]*-1, i});
		dist[i] = t[i]*-1;
	}	
	while(!pq.empty()) {
		int curr, cost;
		cost = pq.top()[0];
		curr = pq.top()[1];
		pq.pop();
		if(dist[curr] < cost)
			continue;
		for(auto x: connected[curr]) {
			int nx, pd;
			nx = x[0];
			pd = x[1];
			if(dist[nx] > cost + pd) {
				dist[nx] = cost+pd;
				pq.push({dist[nx], nx});
			}
		}
	}
	
	for(int i = 1; i <= N; i++) {
		cout << dist[i]*-1 << "\n";
	}
}

 

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

9370 다익스트라

미확인 도착지 목록과 시작점 모두에서 다익스트라를 돌린 후,

(미확인 도착지 - g + 경유지 길이 + h - 시작점) 또는 

(미확인 도착지 - h  + 경유지 길이 + g - 시작점) 이

(시작점 - 미확인도착지) 의 경로의 길이와 같은 경우, 도착지임을 알 수 있다.

#include <bits/stdc++.h>
#define int long long
#define MAX 1000000001
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using p = array<int,2>;
using pp = array<int, 3>;
int32_t main() {
	fastio
	int T;
	cin >> T;
	while(T--) {
		int n, m, t, s, g, h, c;
		cin >> n >> m >> t >> s >> g >> h;
		vector<vector<int>> dist(n+1, vector<int>(n+1, MAX));
		vector<vector<p>> connected(n+1);
		vector<int> v(t);
		for(int i = 0; i < m; i++) {
			int x, y, d;
			cin >> x >> y >> d;
			connected[x].push_back({y, d});
			connected[y].push_back({x, d});
			if((x == g && y == h) || (x == h && y == g)) {
				c = d;
			}
		}		
		priority_queue<pp, vector<pp>, greater<pp>> pq;
		for(int i = 0; i < t; i++) {
			int st;
			cin >> st;
			pq.push({0, st, st});	
			dist[st][st] = 0;
			v[i] = st;
		}	
		pq.push({0, s, s});
		dist[s][s] = 0;
		sort(v.begin(), v.end());
		while(!pq.empty()) {
			int curr, cost, st;
			cost = pq.top()[0];
			curr = pq.top()[1];
			st = pq.top()[2];
			pq.pop();
			if(dist[curr][st] < cost)
				continue;
			for(auto x: connected[curr]) {
				int nx, pd;
				nx = x[0];
				pd = x[1];
				if(dist[nx][st] > cost + pd) {
					dist[nx][st] = cost+pd;
					pq.push({dist[nx][st], nx, st});
				}
			}
		}
		for(int i = 0; i < t; i++) {
			int st = v[i];
			if(dist[g][st] + dist[h][s] + c == dist[s][st] || dist[h][st] + dist[g][s] + c == dist[s][st])
				cout << st << " ";
		}
		cout << "\n";
	}
}

 

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

1854 다익스트라

다익스트라에서 노드가 pop된 횟수는 최단경로의 순서와 같다.

(반드시 pop() 된 시점에 횟수를 증가시켜야 함에 주의)

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000001
using namespace std;
using pi = array<int, 2>;
int main() {
	fastio
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<pi>> connected(n+1);
	vector<vector<int>> dist(n+1, vector<int>(110, MAX));
	vector<int> cnt(n+1, 0);
	for(int i = 0; i < m; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		connected[u].push_back({v, d});
	}
	priority_queue<pi, vector<pi>, greater<pi>> pq;
	pq.push({0, 1});
	for(int i = 1; i <= n; i++) {
		dist[i][0] = 0;
	}
	while(!pq.empty()) {
		int curr, cost;
		cost = pq.top()[0];
		curr = pq.top()[1];
		pq.pop();
		if(cnt[curr] > k)
			continue;
		dist[curr][++cnt[curr]] = cost;
		for(auto x : connected[curr]) {
			int nx, ncost;
			nx = x[0];
			ncost = x[1];
			pq.push({dist[curr][cnt[curr]] + ncost, nx});
		}
	}
	for(int i = 1; i <= n; i++) {
		if(dist[i][k] == MAX)
			cout << "-1\n";
		else
			cout << dist[i][k] << "\n";
	}
}

정석풀이는 상위 K 개 경로 유지 우선순위 큐를 이용한 것이다

 

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000001
using namespace std;
using pi = array<int, 2>;
int main() {
	fastio
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<pi>> connected(n+1);
	vector<priority_queue<int>> r(n+1);
	for(int i = 0; i < m; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		connected[u].push_back({v, d});
	}
	priority_queue<pi, vector<pi>, greater<pi>> pq;
	pq.push({0, 1});
	r[1].push(0);
	while(!pq.empty()) {
		int curr, cost;
		curr = pq.top()[1];
		cost = pq.top()[0];
		pq.pop();
		for(auto x: connected[curr]) {
			int nx, ncost;
			nx = x[0];
			ncost = x[1];
			if(r[nx].size() < k) {
				r[nx].push(cost + ncost);
				pq.push({cost + ncost, nx});
			}
			else if(ncost + cost < r[nx].top()) {
				r[nx].pop();
				r[nx].push(ncost + cost);
				pq.push({cost + ncost, nx});
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		if(r[i].size() < k) {
			cout << "-1\n";
			continue;
		}
		cout << r[i].top() << "\n";
	}
}

 

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

1504 다익스트라

평범한 경유지 다익

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000001
using namespace std;
using pi = array<int, 2>;
using pii = array<int, 3>;
int main() {
	fastio
	int n, e, v1, v2;
	cin >> n >> e;
	vector<vector<pi>> connected(n+1);
	vector<vector<int>> dist(n+1, vector<int>(n+1, MAX));
	for(int i = 0; i < e; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		connected[u].push_back({v, d});
		connected[v].push_back({u, d});
	}
	cin >> v1 >> v2;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	dist[1][1] = dist[v1][v1] = dist[v2][v2] = 0;
	pq.push({0, 1, 1});
	pq.push({0, v1, v1});
	pq.push({0, v2, v2});
	while(!pq.empty()) {
		int curr, cost, st;
		cost = pq.top()[0];
		curr = pq.top()[1];
		st = pq.top()[2];
		pq.pop();
		if(dist[curr][st] < cost)
			continue;
		for(auto x : connected[curr]) {
			int nx, ncost;
			nx = x[0];
			ncost = x[1];
			if(dist[nx][st] > cost + ncost) {
				dist[nx][st] = cost + ncost;
				pq.push({dist[nx][st], nx, st});
			}
		}
	}
	int ans = MAX;
	if(dist[v1][1] != MAX && dist[v2][v1] != MAX && dist[n][v2] != MAX)
		ans = min(ans, dist[v1][1] + dist[v2][v1] + dist[n][v2]);
	
	if(dist[v2][1] != MAX && dist[v1][v2] != MAX && dist[n][v1] != MAX)
		ans = min(ans, dist[v2][1] + dist[v1][v2] + dist[n][v1]);
	
	if(ans == MAX)
		cout << "-1";
	else
		cout << ans;
}

 

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

35415 다익스트라

다익 3번 돌리고, 방문순서 고려해서 최단경로 구하는 경유지 다익

#include <bits/stdc++.h>
#define int long long
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX LLONG_MAX
using namespace std;
using pi = array<int, 2>;
using pii = array<int, 3>;
void f(vector<int>& dist, vector<vector<pi>>& connected, int s) {
	priority_queue<pi, vector<pi>, greater<pi>> pq;
	pq.push({0, s});
	dist[s] = 0;
	while(!pq.empty()) {
		int curr, cost;
		cost = pq.top()[0];
		curr = pq.top()[1];
		pq.pop();
		if(dist[curr] < cost)continue;
		for(auto x : connected[curr]) {
			int nx, ncost;
			nx = x[0];
			ncost = x[1];
			if(dist[nx] > cost + ncost) {
				dist[nx] = cost + ncost;
				pq.push({dist[nx], nx});
			}
		}
	}
}
int32_t main() {
	fastio
	int N, M, K, T;
	cin >> N >> M >> K >> T;
	vector<int> dist1(N+1, MAX), dist2(N+1, MAX), dist3(N+1, MAX);
	vector<vector<pi>> connected(N+1);
	for(int i = 0; i < M; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		connected[u].push_back({v, d});
		connected[v].push_back({u, d});
	}
	for(int i = 1; i <= N; i++) {
		sort(connected[i].begin(), connected[i].end());
	}
	priority_queue<int, vector<int>, greater<int>> pq;
	f(dist1, connected, 1);
	f(dist2, connected, K);
	f(dist3, connected, N);
	int ans = MAX;
	for(int i = 1; i <= N; i++) {
		if(i == K) {
			if(dist1[K] == MAX || dist3[K] == MAX)
				continue;
			ans = min(ans, dist1[K] + dist3[K]);
			continue;
		}
		if(dist2[i] > T)continue;
		if(dist1[i] == MAX || dist3[i] == MAX)
			continue;
		ans = min(ans, dist1[i] + T + dist3[i]);
	}
	if(ans == MAX)
		cout << "-1";
	else
		cout << ans;
}

 

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

7812 트리 dp

루트노드에서 일단 한번 모든 노드까지의 거리 합을 구한 후, 

옮길 때 마다 서브트리의 크기를 이용하여 거리합을 갱신하는 점화식을 생각해야 하는 문제

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

using pi = array<int, 2>;

vector<int> dp, cnt;

vector<vector<pi>> connected, children;

void make_tree(int node, int p) {

   for(auto x : connected[node]) {

      int c, d;

      c = x[0];

      d = x[1];

      if(c == p)continue;

      children[node].push_back({c, d});

      make_tree(c, node);

   }

}

void fill_first_node(int curr, int sum) {

   for(auto x : children[curr]) {

      int c, d;

      c = x[0];

      d = x[1];
   
      dp[0] += (sum+d);

      fill_first_node(c, sum+d);

   }

}

void cnt_node(int curr) {

   cnt[curr] = 1;

   for(auto x : children[curr]) {

      int c = x[0];

      cnt_node(c);

      cnt[curr] += cnt[c];

   }

}

void solve(int curr, int N) {

   for(auto x : children[curr]) {

      int c, d;

      c = x[0];

      d = x[1];

      dp[c] = dp[curr] - cnt[c]*d + (N-cnt[c])*d;

      solve(c, N); 

   }

}

int32_t main() {

   while(1) {

      int N;

      cin >> N;

      if(N == 0)break;
if(N==1) {
    cout << "0\n";
    continue;
   }
      children.assign(N, vector<pi>(0));

      connected.assign(N, vector<pi>(0));

      dp.assign(N, 0);

      cnt.assign(N, 0);

      for(int i = 0; i < N-1; i++) {

         int u, v, d;

         cin >> u >> v >> d;

         connected[u].push_back({v, d});

         connected[v].push_back({u, d});

      }

      make_tree(0, -1);

      fill_first_node(0, 0);

      cnt_node(0);

      solve(0, N);

      int ans = 9999999999999;

      for(int i = 0; i < N; i++) {

         ans = min(ans, dp[i]);

      }

      cout << ans << "\n";

   }

}

 

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

2463 오프라인 쿼리, 분리집합

작은 것 부터 삭제한다는 것은 큰 것 부터 잇는다는 뜻.

고려하지 않아도 되는 계산을 영리하게 제외하는 것이 매우 어려운 것 같다.

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000000
using namespace std;
using pii = array<int, 3>;

vector<int> parent, cnt;
priority_queue<pii> pq;
int f(int x) {
	if(x == parent[x])
		return x;
	return parent[x] = f(parent[x]);
}

bool issame(int a, int b) {
	return a == b;
}

void Union(int a, int b) {
	parent[a] = b;
	cnt[b] += cnt[a];
}

int32_t main() {
	int N, M, ans = 0, cost = 0;
	cin >> N >> M;
	parent.resize(N+1);
	cnt.resize(N+1);
	for(int i = 1; i <= N; i++) {
		parent[i] = i;
		cnt[i] = 1;
	}
	
	for(int i = 1; i <= M; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		pq.push({d, u, v});
		cost += d;
	}
	while(!pq.empty()) {
		int u, v, d;
		u = f(pq.top()[1]);
		v = f(pq.top()[2]);
		d = pq.top()[0];
		pq.pop();
		if(!issame(u, v)) {
			ans += cnt[u] * cnt[v] * cost;
			ans %= MOD;
			Union(u, v);
		}
		cost -= d;
	}
	cout << ans;
}

 

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

17398 오프라인 쿼리

제거한 순서의 역순으로 연결한다는 동일한 아이디어

 

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000000
using namespace std;
using pii = array<int, 3>;

vector<int> parent, cnt;
priority_queue<pii> pq;
int f(int x) {
	if(x == parent[x])
		return x;
	return parent[x] = f(parent[x]);
}

bool issame(int a, int b) {
	return a == b;
}

void Union(int a, int b) {
	parent[a] = b;
	cnt[b] += cnt[a];
}

int32_t main() {
	int N, M, ans = 0, cost = 0;
	cin >> N >> M;
	parent.resize(N+1);
	cnt.resize(N+1);
	for(int i = 1; i <= N; i++) {
		parent[i] = i;
		cnt[i] = 1;
	}
	
	for(int i = 1; i <= M; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		pq.push({d, u, v});
		cost += d;
	}
	while(!pq.empty()) {
		int u, v, d;
		u = f(pq.top()[1]);
		v = f(pq.top()[2]);
		d = pq.top()[0];
		pq.pop();
		if(!issame(u, v)) {
			ans += cnt[u] * cnt[v] * cost;
			ans %= MOD;
			Union(u, v);
		}
		cost -= d;
	}
	cout << ans;
}

 

 

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

 

12012 오프라인 쿼리, 분리집합

그래프의 완전 연결 여부를 check 하는 방법을 새롭게 배워간 문제.

컴포넌트 수를 잘 세어줘야 한다.

 

#include <bits/stdc++.h>
using namespace std;
using pi = array<int, 2>;
vector<int> parent, query, cnt;
vector<vector<int>> connected;
map<int, bool> present;
vector<string> ans;
int f(int x) {
	if(x == parent[x])
		return x;
	return parent[x] = f(parent[x]);
}

int main() {
	int N, M;
	cin >> N >> M;
	parent.resize(N+1);
	connected.resize(N+1);
	cnt.resize(N+1, 1);
	for(int i = 1; i <= N; i++) {
		parent[i] = i;
	}
	for(int i = 1; i <= M; i++) {
		int u, v;
		cin >> u >> v;
		connected[u].push_back(v);
		connected[v].push_back(u);
	}
	for(int i = 0; i < N; i++) {
		int x; cin >> x;
		query.push_back(x);
	}
	int root = query[N-1];
	present[root] = true;
	ans.push_back("YES");
	for(int i = N-2; i >= 0; i--) {
		int u = query[i];
		present[u] = true;
		for(int v : connected[u]) {
			if(f(u) == f(v))continue;
			if(present[v]) {
               int fu = f(u);
                int fv = f(v);
				parent[fu] = fv;
				cnt[fv] += cnt[fu];
			}
		}
		if(cnt[f(u)] == N-i) {
			ans.push_back("YES");
		}
		else {
			ans.push_back("NO");
		}
 	}
	for(int i = N-1; i >= 0; i--) {
		cout << ans[i] << "\n";
	}
}

 

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

11266 단절점

 

새롭게 배운 개념이다. 포스팅 예정.

 

#include <bits/stdc++.h>
using namespace std;
using pi = array<int, 2>;

vector<int> low, parent, order;
vector<vector<int>> connected;
map<int, bool> cut;
int ans, cnt;
void dfs(int x) {
	int children = 0;
	order[x] = ++cnt;
	low[x] = order[x];
	for(int nx : connected[x]) {
		if(nx == parent[x])continue;
		if(order[nx] == -1) {
			children++;
			parent[nx] = x;
			dfs(nx);
			if(parent[x] != -1 && low[nx] >= order[x] && !cut[x]) {
				cut[x] = true;
				ans++;
			}
            low[x] = min(low[x], low[nx]);
		}
		else {
			low[x] = min(low[x], order[nx]);
		}
	}
	if(parent[x] == -1 && children >= 2) {
		cut[x] = true;
		ans++;
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	connected.resize(N+1, vector<int>(0));
	low.resize(N+1);
	parent.resize(N+1, -1);
	order.resize(N+1, -1);
	
	for(int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		connected[u].push_back(v);
		connected[v].push_back(u);
	}
	for(int i = 1; i <= N; i++) {
		if(order[i] == -1) 
			dfs(i);
	}
	cout << ans << "\n";
	
	for(int i = 1; i <= N; i++) {
		if(cut[i])cout << i << " "; 
	}
}