2022.07.19. 복습 2 풀이

다뤄본 태그

• Exponentiation By Squaring, Modular Multiplicative Inverse (Fermat's Little Theorem)
• Primality Test, Prime Factorization, Sieve of Eratosthenes
• Sweeping
• Minimum Spanning Tree (Kruskal, Prim)
• DIsjoint-Set Union (Union-Find)
• Depth First Search, Breadth First Search, Dijkstra, Bellman-Ford, Floyd-Warshall, 0-1 BFS
• Directed Acyclic Graph, Topological Sort
• Tree
• Tree DP, Bitwise DP

A. [11653] 소인수분해 (Bronze I)

의도한 태그: Prime Factorization

어떤 수가 소수인지 판별할 때, sqrt N까지 나눠봤었죠? 비슷하게 해주면 됩니다.

 

만약 sqrt N까지 나눠봐도 나누지를 못해서 N이 남았다면, 이는 따로 출력해주면 됩니다.

void Main(){
	int n; cin >> n;
	for (ll p = 2; p*p <= n; p++){
		while (n%p == 0){ cout << p << endl; n /= p; }
	}
	if (n != 1){ cout << n; }
}

B. [1978] 소수 찾기 (Silver V)

의도한 태그: Primality Test

수를 입력받아서, 2부터 N까지 일일이 나눠보면 됩니다.

N = 1일 때의 예외처리에 주의하세요.

void Main(){
	int ans = 0;
	int t; cin >> t; while (t--){
		int n; cin >> n;
		bool flg = (n != 1);
		for (int p = 2; p < n; p++){ flg &= (n % p != 0); }
		ans += flg;
	}
	cout << ans;
}

C. [13171] A (Silver IV)

의도한 태그: Exponentiation By Squaring

\( A^{B} = A^{B/2} \times A^{B/2} \)임을 사용해서, \( O(\log B) \) 시간에 계산해주면 됩니다.

const ll mod = 1e9 + 7;

ll fpow(ll a, ll b){
	ll res = 1;
	while (b){
		if (b & 1){ res = res*a % mod; }
		a = a*a % mod; b >>= 1;
	}
	return res;
}

void Main(){
	ll a, b; cin >> a >> b; a %= mod; cout << fpow(a, b);
}

D. [15922] 아우으 우아으이야!! (Gold V)

의도한 태그: Sweeping

\( i \)번째 구간을 보고 있고, 그 때 관리하고 있던 구간이 \( [L, R] \)이라고 합시다.

그럼 각 경우에 따라서 관리하는 구간을 바꿔주면 됩니다.

• \( R < L_{i} \): 두 구간이 겹치지 않는 경우입니다. 그러니, 관리하던 구간의 길이를 답에 더한 뒤, \( [L_{i}, R_{i}] \)를 새로 관리하는 구간으로 지정해주면 됩니다.
• else: 두 구간이 겹치는 경우입니다. 그러니, 관리하는 구간을 \( [L, \max(R, R_{i})] \)로 변경해주면 됩니다.

pl2 arr[100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	ll ans = 0, stp = -1e15, edp = -1e15;
	for (int i = 1; i <= n; i++){
		ll st = arr[i].fr, ed = arr[i].sc;
		if (edp < st){ ans += edp-stp; stp = st; edp = ed; }
		else{ edp = max(edp, ed); }
	}
	ans += edp-stp; cout << ans;
}

E. [15681] 트리와 쿼리 (Gold V)

의도한 태그: Tree DP

\( D_{v} = v \)를 루트로 하는 서브트리의 정점 개수 를 정의해봅시다.

그러면, \( v \)의 자식 \( w \)에 대하여, \( D_{v} = \sum D_{w} + 1 \)이 됩니다.

vector<int> adj[100020];

int dp[100020];
void dpf(int now, int pre){
	dp[now] = 1;
	for (int nxt : adj[now]){
		if (nxt == pre){ continue; }
		dpf(nxt, now); dp[now] += dp[nxt];
	}
}

void Main(){
	int n, r, q; cin >> n >> r >> q;
	for (int i = 1; i < n; i++){
		int v, w; cin >> v >> w;
		adj[v].push_back(w); adj[w].push_back(v);
	}
	dpf(r, -1);
	while (q--){
		int v; cin >> v; cout << dp[v] << endl;
	}
}

F. [10026] 적록색약 (Gold V)

의도한 태그: Depth First Search

R, G, B로 구역의 수를 구한 뒤, 모든 G를 R로 바꾸고 구역의 수를 다시 구해주면 됩니다.

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};

int n; char mp[120][120];

bool chk[120][120];
void dfs(int y, int x){
	chk[y][x] = 1; //cout << "DFS " << y << ' ' << x << endl;
	for (int d = 0; d < 4; d++){
		int yy = y+dy[d], xx = x+dx[d];
		if (1 > yy || yy > n){ continue; }
		if (1 > xx || xx > n){ continue; }
		if (chk[yy][xx]){ continue; }
		if (mp[yy][xx] != mp[y][x]){ continue; }
		//cout << "D " << yy << ' ' << xx << endl;
		dfs(yy, xx);
	}
}

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cin >> mp[i][j]; }
	}
	int c1 = 0, c2 = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (!chk[i][j]){ c1 += 1; dfs(i, j); }
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (mp[i][j] == 'G'){ mp[i][j] = 'R'; }
			chk[i][j] = 0;
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (!chk[i][j]){ c2 += 1; dfs(i, j); }
		}
	}
	cout << c1 << ' ' << c2;
}

G. [13172] Σ (Gold IV)

의도한 태그: Moduler Multiplicative Inverse

페르마의 소정리에 의해, 소수 \( p \)에 대하여 \( A_{p} \equiv A \pmod p \)이므로, \( A_{p-2} \equiv A^{-1} \pmod p \)가 됩니다.

문제의 답은 그냥 \( n, s \)가 주어질 때, \( s \times n^{-1} \)을 합해서 출력하면 됩니다.

const ll mod = 1e9 + 7;

ll fpow(ll a, ll b){
	ll res = 1;
	while (b){
		if (b & 1){ res = res*a % mod; }
		a = a*a % mod; b >>= 1;
	}
	return res;
}
inline ll finv(ll a){ return fpow(a, mod-2); }

void Main(){
	int n; cin >> n;
	ll ans = 0;
	while (n--){
		ll a, b; cin >> a >> b;
		ll res = b * finv(a) % mod;
		ans += res; ans %= mod;
	}
	cout << ans;
}

H. [11657] 타임머신 (Gold IV)

의도한 태그: Bellman-Ford

음수 가중치가 있을 수 있는 가중치 그래프에서 최단 경로를 구하는 문제니, 벨만 포드를 그대로 구현해주면 됩니다.

vector<pi3> edg;
const ll INF = 1e15; ll dis[520];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 2; i <= n; i++){ dis[i] = INF; }
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		edg.push_back({ {v, w}, x });
	}
	for (int t = 1; t <= n; t++){
		for (pi3 p : edg){
			int v = p.fr.fr, w = p.fr.sc, x = p.sc;
			if (dis[v] == INF){ continue; }
			if (dis[w] <= dis[v]+x){ continue; }
			dis[w] = dis[v] + x; if (t == n){ cout << -1; return; }
		}
	}
	for (int i = 2; i <= n; i++){
		cout << (dis[i] == INF ? -1 : dis[i]) << endl;
	}
}

I. [9019] DSLR (Gold IV)

의도한 태그: Breadth First Search

0000부터 9999까지의 수를 정점으로 놓으면, D S L R의 연산으로 간선을 만든 뒤

최단 경로를 찾는 문제가 됩니다.

int dis[10020]; pic pre[10020];

void Main(){
	int t; cin >> t; while (t--){
		int st, ed; cin >> st >> ed;
		queue<int> q; q.push(st);
		memset(dis, -1, sizeof(dis)); dis[st] = 0;
		while (!q.empty()){
			int now = q.front(); q.pop();
			//cout << "Q " << now << endl << flush;
			pic p1 = { (now*2) % 10000, 'D' };
			pic p2 = { (now+9999) % 10000, 'S' };
			pic p3 = { (now*10)%10000 + (now/1000), 'L' };
			pic p4 = { (now/10) + (now%10)*1000, 'R' };
			for (pic p : {p1, p2, p3, p4}){
				int nxt = p.fr; char ch = p.sc;
				//cout << "NEXT " << nxt << ' ' << ch << endl << flush;
				if (dis[nxt] != -1){ continue; }
				dis[nxt] = dis[now] + 1; pre[nxt] = {now, ch};
				q.push(nxt);
			}
		}
		int ptr = ed; stack<char> ans;
		while (ptr != st){
			ans.push(pre[ptr].sc); ptr = pre[ptr].fr;
		}
		while (!ans.empty()){ cout << ans.top(); ans.pop(); } cout << endl;
	}
}

J. [1717] 집합의 표현 (Gold IV)

의도한 태그: Disjoint-Set Union (Union Find)

0번 쿼리는 그냥 Union 연산이고, 1번 쿼리는 두 정점에 Find 연산을 적용시킨 뒤 동일한 지 판별해주면 됩니다.

int par[1000020];
int fnd(int v){ return par[v] = (par[v] == v ? v : fnd(par[v])); }
void uni(int v, int w){ par[fnd(w)] = fnd(v); }

void Main(){
	int n, q; cin >> n >> q;
	for (int i = 0; i <= n; i++){ par[i] = i; }
	while (q--){
		int typ; cin >> typ;
		if (typ == 0){ int v, w; cin >> v >> w; uni(v, w); }
		if (typ == 1){
			int v, w; cin >> v >> w;
			cout << (fnd(v)==fnd(w) ? "YES" : "NO") << endl;
		}
	}
}

K. [11404] 플로이드 (Gold IV)

의도한 태그: Floyd-Warshall

BFS를 N번 돌리는 것도 방법이겠지만, 이렇게 N 제한이 작을 때는 구현이 편한 플로이드를 돌리는 것도 좋습니다.

const int INF = 1e9; int adj[120][120];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ adj[i][j] = (i==j ? 0 : INF); }
	}
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v][w] = min(adj[v][w], x);
	}
	for (int u = 1; u <= n; u++){
		for (int v = 1; v <= n; v++){
			for (int w = 1; w <= n; w++){
				adj[v][w] = min(adj[v][w], adj[v][u] + adj[u][w]);
			}
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cout << adj[i][j] << ' '; }
		cout << endl;
	}
}

L. [16563] 어려운 소인수분해 (Gold III)

에라토스테네스의 체를 돌릴 때, 소수인지 판정을 하는 대신 어떤 수를 나누는 가장 작은 소인수를 저장해봅시다.

이는 에라토스테네스의 체에서 수를 제거할 때마다, 어떤 소수에 의해 제거되는지 저장해두면 됩니다.

 

소인수분해는 \( x \)를 나누는 가장 작은 소인수 \( p \)를 찾은 뒤, \( x \)를 \( p \)로 나누고, 이 과정을 \( x \)가 1이 될 때까지 반복해주면 됩니다.

const int N = 5000000; int pr[5000020];

void Main(){
	for (int i = 2; i <= N; i++){
		if (pr[i] != 0){ continue; }
		for (int j = i; j <= N; j+=i){ if (pr[j] == 0){ pr[j] = i; } }
	}
	int t; cin >> t; while (t--){
		int x; cin >> x;
		while (x > 1){ int p = pr[x]; cout << p << ' '; x /= p; }
		cout << endl;
	}
}

M. [14621] 나만 안되는 연애 (Gold III)

의도한 태그: Minimum Spanning Tree (Kruskal)

2, 3번 조건은 그냥 MST를 구하라는 조건입니다.

그럼 고려해야 할 건 1번 조건밖에 없는데, 이는 SMT를 돌리기 전에 남초와 여초를 잇는 간선만 남겨주면 됩니다.

char arr[1020];

int par[1020];
int fnd(int v){ return par[v] = (par[v]==v ? v : fnd(par[v])); }
void uni(int v, int w){ par[fnd(w)] = fnd(v); }

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){ par[i] = i; }
	priority_stack<pi3> pq;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		if (arr[v] != arr[w]){ pq.push({ x, {v, w} }); }
	}
	int ans = 0, cnt = 0;
	while (!pq.empty()){
		int v = pq.top().sc.fr, w = pq.top().sc.sc, x = pq.top().fr;
		pq.pop();
		if (fnd(v) != fnd(w)){ uni(v, w); ans += x; cnt += 1; }
	}
	cout << (cnt==n-1 ? ans : -1);
}

N. [20390] 완전그래프의 최소 스패닝 트리 (Gold II)

의도한 태그: Minimum Spanning Tree (Prim)

메모리가 16MB밖에 없기 때문에, \( O(N^2) \)개의 간선을 모두 저장할 수는 없습니다.

그래서 Prim 알고리즘을 쓰면서 각 정점에 연결된 간선 가중치의 최솟값만을 저장해주면 됩니다.

INF = 10**15
n = int( input() )
a, b, c, d = tuple( map( int, input().split() ) )
arr = list( map( int, input().split() ) )
dis = [ (arr[0]*a + arr[i]*b) % c ^ d for i in range(n) ]
chk = [ i==0 for i in range(n) ]
ans = 0
for i in range(n-1):
    mn, mnp = INF, 0
    for j in range(n):
        if chk[j]: continue
        if dis[j] < mn: mn, mnp = dis[j], j
    ans += mn; chk[mnp] = True
    for j in range(n):
        dis[j] = min(dis[j], (arr[min(mnp,j)]*a + arr[max(mnp,j)]*b) % c ^ d)
print(ans)

O. [5827] What's Up With Gravity (Gold II)

의도한 태그: 0-1 BFS

(y, x, 중력 방향)을 정점으로 놓고, 가로/세로 이동 및 중력에 의해 떨어지는 이동은 0의 가중치를, 중력 반전은 1의 가중치를 가지는 간선을 설정하면 0-1 BFS를 사용해서 풀 수 있습니다.

char mp[520][520];
int dis[520][520][2];

void Main(){
	int n, m; cin >> n >> m;
	pi2 st, ed;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> mp[i][j];
			if (mp[i][j] == 'C'){ st = {i, j}; mp[i][j] = '.'; }
			if (mp[i][j] == 'D'){ ed = {i, j}; mp[i][j] = '.'; }
		}
	}
	memset(dis, -1, sizeof(dis));
	deque<pi4> q; q.push_front({ st, {0, 0} }); dis[st.fr][st.sc][0] = 0;
	while (!q.empty()){
		int y = q.front().fr.fr, x = q.front().fr.sc;
		int dir = q.front().sc.fr, dst = q.front().sc.sc;
		//cout << "DQ " << y << ' ' << x << ' ' << dir << " - " << dst << endl;
		q.pop_front();
		if (mkp(y, x) == ed){ cout << dst; return; }
		int yy = (dir==0 ? y+1 : y-1), xx = x;
		if (1 > yy || yy > n){ continue; }
		if (mp[yy][xx] == '.'){
			q.push_front({ {yy, xx}, {dir, dst} });
			dis[yy][xx][dir] = dst;
		}
		else{
			int yy = y; for (int xx : {x-1, x+1}){
				if (1 > xx || xx > n){ continue; }
				if (mp[yy][xx] == '#'){ continue; }
				if (dis[yy][xx][dir] != -1){ continue; }
				q.push_front({ {yy, xx}, {dir, dst} });
				dis[yy][xx][dir] = dst;
			}
			if (dis[y][x][dir^1] != -1){ continue; }
			q.push_back({ {y, x}, {dir^1, dst+1} });
			dis[y][x][dir^1] = dst+1;
		}
	}
	cout << -1;
}

P. [2637] 장난감 조립 (Gold II)

의도한 태그: Topological Sort, DAG DP

로봇의 조립 과정을 그래프로 나타내면, DAG가 나옵니다.

DAG 위에서는 DP를 돌릴 수 있고, 이는 \( D_{i, j} = i \)번 부품을 만들기 위해 필요한 \( j \)번 (기본) 부품의 개수 로 간단히 해결할 수 있습니다.

남은 건 DAG의 정점을 탐색하는 방법으로, DFS 방문 순서의 역순이 위상정렬임을 생각해보면

그냥 평소에 재귀 dp 돌리듯이 탐색해주면 된다는 걸 알 수 있습니다.

ll dp[120][120];
vector<pi2> adj[120]; int par[120];

bool chk[120];
void dpf(int now){
	chk[now] = 1;
	if (adj[now].size() == 0){ dp[now][now] = 1; return; }
	for (pi2 p : adj[now]){
		int nxt = p.fr, x = p.sc;
		if (!chk[nxt]){ dpf(nxt); }
		for (int i = 1; i <= 100; i++){ dp[now][i] += x*dp[nxt][i]; }
	}
}

void Main(){
	int n, m; cin >> n >> m;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x});
	}
	dpf(n);
	for (int i = 1; i <= n; i++){
		if (dp[n][i] > 0){ cout << i << ' ' << dp[n][i] << endl; }
	}
}

Q. [9370] 미확인 도착지 (Gold II)

예술가들의 경로는 \( s \Rightarrow g \rightarrow h \Rightarrow e \) 또는 \( s \Rightarrow h \rightarrow g \Rightarrow e \)로 나타낼 수 있습니다.

그러니 \( s \Rightarrow g \rightarrow h \Rightarrow e \) 또는 \( s \Rightarrow h \rightarrow g \Rightarrow e \)의 길이가 \( s \Rightarrow e \)와 같은 정점들이 있는지 보면 됩니다.

 

그러니 \( s, g, h \)에서 다른 모든 정점으로 가는 경로를 미리 계산해주고, 위와 같이 처리해주면 됩니다.

const ll INF = 1e15;
int n, m, k;
vector<pl2> adj[2020];
ll dis[3][2020];

void f(int st, int idx){
	for (int i = 1; i <= n; i++){ dis[idx][i] = INF; }
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, st}); dis[idx][st] = 0;
	while (!pq.empty()){
		ll dst = pq.top().fr; int now = pq.top().sc;
		pq.pop();
		if (dst != dis[idx][now]){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[idx][nxt] <= d+dst){ continue; }
			dis[idx][nxt] = d+dst;
			pq.push({dis[idx][nxt], nxt});
		}
	}
}

void Main(){
	int t; cin >> t;
	while (t--){
		cin >> n >> m >> k;
		int st, x, y; cin >> st >> x >> y;
		ll d = 0;
		while (m--){
			int a, b, c; cin >> a >> b >> c;
			if (a==x && b==y || a==y && b==x){ d = c; }
			adj[a].push_back({b, c}); adj[b].push_back({a, c});
		}
		f(st, 0); f(x, 1); f(y, 2);
		vector<int> ans;
		while (k--){
			int a; cin >> a;
			//cout << "A  " << a << endl;
			//cout << "D1 " << dis[0][a] << endl;
			//cout << "D2 " << dis[0][x] + d + dis[2][a] << endl;
			//cout << "D3 " << dis[0][y] + d + dis[1][a] << endl;
			if (dis[0][a] == dis[0][x] + d + dis[2][a] || dis[0][a] == dis[0][y] + d + dis[1][a]){ ans.push_back(a); }
		}
		sort( all(ans) );
		for (int x : ans){ cout << x << ' '; }
		cout << endl;
		for (int i = 1; i <= n; i++){ adj[i].clear(); }
	}
}

R. [2263] 트리의 순회 (Gold II)

의도한 태그: Tree

트리의 inorder 순회를 1, 2, 3, ...이 되도록 정점에 번호를 다시 매겨봅시다. (cvt)

대신에, 나중에 출력할 때는 이러한 번호 매기기의 역연산을 해줘야겠죠. (tvc)

 

그러면 남은 건 postorder 뿐입니다.

postorder의 특징은, 현재 보는 서브트리의 루트가 맨 마지막에 있다는 점입니다.

그러니, 서브트리의 루트를 바로 찾을 수 있습니다.

 

이제 정렬된 inorder의 특징으로, inorder가 정렬되었다면

현재 루트 정점이 v번일 때, v보다 작은 정점들은 왼쪽에, 큰 정점들은 오른쪽에 있게 됩니다.

그러니 이 위치가 바뀌는 부분을 postorder에서 이진 탐색 등으로 적절히 찾아준 뒤, 재귀적으로 처리해주면 됩니다.

int cvt[100020], tvc[100020];
int n; int arr[100020];

void dnc(int st, int ed, int dep = 0){
	//for (int i = 0; i < dep; i++){ cout << "  "; } cout << st << ' ' << ed << endl;
	if (st > ed){ return; }
	int res = arr[ed]; cout << tvc[res] << ' ';
	if (st == ed){ return; }
	if (arr[st] > res){ return dnc(st, ed-1, dep+1); }
	int l = st, r = ed;
	while (l+1 <= r-1){
		int mid = l+r >> 1;
		if (arr[mid] <= res){ l = mid; } else{ r = mid; }
	}
	dnc(st, l, dep+1); dnc(r, ed-1, dep+1);
}

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		int x; cin >> x; cvt[x] = i; tvc[i] = x;
	}
	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		arr[i] = cvt[x];
	}
	dnc(1, n);
}

S. [2098] 외판원 순회 (Gold I)

의도한 태그: Bit DP

\( D_{v, bit} = \) 현재 방문 상태를 비트마스킹한 상태가 \( bit \)이고, 현재 \( v \)번 정점에 있을 때 최소 비용

으로 정의하면, 다음 정점으로 갈 때마다 비트를 잘 갱신하면서 DP를 돌려주면 됩니다.

const int INF = 1e9;

int n, ful;
int dp[20][65540];
int adj[20][20];

int dpf(int now, int chk){
	if (dp[now][chk] != INF){ return dp[now][chk]; }
	if (chk == ful){ return dp[now][chk] = adj[now][0]; }
	int res = INF;
	for (int nxt = 0; nxt < n; nxt++){
		if (chk>>nxt & 1){ continue; }
		res = min( res, dpf(nxt, chk | 1<<nxt) + adj[now][nxt] );
	}
	if (res == INF){ res += 1; }
	return dp[now][chk] = res;
}

void Main(){
	cin >> n; ful = (1<<n) - 1;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			cin >> adj[i][j];
			if (adj[i][j] == 0){ adj[i][j] = INF; }
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j <= ful; j++){ dp[i][j] = INF; }
	}
	cout << dpf(0, 1);
}