Problem Solving

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5925 🧐 관찰 및 접근 # X로 그려지는 영역이 3개가 있고, 최소한의 비용으로 이들을 연결해야한다. 멀티 소스 BFS와 같은 맛으로 가능할 것 같다. 3개니까 전수조사 해도 되겠지. 아, 근데 좀 사고인 경우가 있구나. ..... ..X.. .X.X. ..... 위와 같은 경우에, 하나만으로도 칠할 수 있는 것 같다. 위와 같은 경우에, 세 그룹이 한 정점에서 무조건 모이게 된다. 따라서 빈 정점을 잡고, 거기서 세 그룹까지의 최단경로를 이용하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<string> S(N); rep(i, 0, N) cin >> S[i]; vector<vector<int>> board(N, vector<int>(M)); int color = 0; rep(i, 0, N) rep(j, 0, M) { if(S[i][j] == 'X' && board[i][j] == 0){ queue<pii> Q; Q.push({i, j}); board[i][j] = ++color; while(!Q.empty()){ auto [cx, cy] = Q.front(); Q.pop(); rep(d, 0, 4){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(S[nx][ny] == 'X' && board[nx][ny] == 0){ board[nx][ny] = color; Q.push({nx, ny}); } } } } } vector<ll> dists; auto getDist = [&](int c1, int c2) -> ll { vector<vector<int>> dist(N, vector<int>(M, -1)); queue<pii> Q; rep(i, 0, N) rep(j, 0, M){ if(board[i][j] == c1){ dist[i][j] = 0; Q.push({i, j}); } } while(!Q.empty()){ auto [cx, cy] = Q.front(); Q.pop(); rep(d, 0, 4){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(board[nx][ny] == c2){ return dist[cx][cy]; } if(board[nx][ny] == 0 && dist[nx][ny] == -1){ dist[nx][ny] = dist[cx][cy] + 1; Q.push({nx, ny}); } } } return (ll)1e18; }; rep(i, 1, 4) rep(j, i+1, 4) dists.push_back(getDist(i, j)); sort(all(dists)); ll ans = dists[0] + dists[1]; auto getDist2 = [&](int cx, int cy, int c) -> ll { vector<vector<int>> dist(N, vector<int>(M, -1)); queue<pii> Q; dist[cx][cy] = 0; Q.push({cx, cy}); while(!Q.empty()){ auto [x, y] = Q.front(); Q.pop(); rep(d, 0, 4){ int nx = x + dx[d]; int ny = y + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(board[nx][ny] == c){ return dist[x][y]; } if(board[nx][ny] == 0 && dist[nx][ny] == -1){ dist[nx][ny] = dist[x][y] + 1; Q.push({nx, ny}); } } } return (ll)1e18; }; rep(i, 0, N) rep(j, 0, M) if(board[i][j] == 0){ ans = min(ans, getDist2(i, j, 1) + getDist2(i, j, 2) + getDist2(i, j, 3) + 1); } cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/33527 🧐 관찰 및 접근 # 뭔가 전반적으로 세팅이 BOJ 5214 환승이 생각나는 것 같기도? 나이브하게 돈다면, 각 노선에 있을 수 있는 최대 정류장 수가 10만개니까, 이걸 다 돌기 시작하면 상당히 막막해진다. 그림을 그려서 어떤 상황인지 더 잘 판단해보자. 일단 예제 1번은 이런데, 흠. 확실히 정류장보단 노선 단위로 어떻게 잘 보고싶긴 하다. 노선은 총 $5 \times X = 500$개이다. 이때, 노선의 환승 각 정류장 $N$개마다 $\binom{5}{2}$ 개이므로 최대 $100\,000 \times = 1\,000\,000$개인 것 같다. 중복도 제거할수도 있고. 아? 이게 노선이 충분히 적으니, 플로이드 워셜이 가능해보인다. 쿼리는 정점에 대해 들어오니, $U_i, V_i$가 각각 5개 노선에 속하는 경우 25가지에 대해 노선으로 계산하면 될 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N, X; cin >> N >> X; vector<array<int, 5>> bus(N); rep(i, 0, N) rep(j, 0, 5) cin >> bus[i][j]; auto toIdx = [&](pii p){ return p.first*X + (p.second - 1); }; vector<vector<int>> dist(5*X, vector<int>(5*X, 1e9)); rep(i, 0, 5*X) dist[i][i] = 0; rep(i, 0, N) rep(j, 0, 5) rep(k, j+1, 5){ int u = toIdx({j, bus[i][j]}), v = toIdx({k, bus[i][k]}); dist[u][v] = dist[v][u] = 1; } rep(k, 0, 5*X) rep(i, 0, 5*X) rep(j, 0, 5*X) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); int Q; cin >> Q; while(Q--){ int u, v; cin >> u >> v; int ans = 1e9; rep(i, 0, 5) rep(j, 0, 5){ int idx_u = toIdx({i, bus[u-1][i]}), idx_v = toIdx({j, bus[v-1][j]}); ans = min(ans, dist[idx_u][idx_v]); } cout << (ans == 1e9 ? -1 : ans+1) << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32655 🧐 관찰 및 접근 # 시작 정점에서 각 출구로 갈 수 있는 최단 경로를 구한 후, 열리는 타이밍에 맞춰 나갈 수 있는 최소 시간을 구하자. $KX$초 단위로 출구가 도는게 로테이션 돌고, 이분탐색으로 그 타이밍을 찾은 후 그 블럭에서 나갈 수 있는지, 그 다음블럭에서 나갈 수 있는지 체크하면 될 것 같다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M, K; cin >> N >> M >> K; vector<vector<pll>> links(N+1); rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } vector<ll> dist(N+1, LLONG_MAX); priority_queue<pll, vector<pll>, greater<pll>> pq; dist[1] = 0; pq.push({0, 1}); while(!pq.empty()){ auto [cd, cur] = pq.top(); pq.pop(); if(dist[cur] < cd) continue; for(auto [nxt, w]: links[cur]){ ll nd = cd + w; if(nd < dist[nxt]){ dist[nxt] = nd; pq.push({nd, nxt}); } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23807 🧐 관찰 및 접근 # 무향그래프고, 정해진 정점중 세개 이상의 정점을 지나야 한다.. 이걸 경로로 나타내면 $X \rightarrow P_i \rightarrow P_j \rightarrow P_k \rightarrow Z$이 될 것이다. 이때, $X$에서 시작한 경로와 $Z$에서 시작한 최단 경로는 다익스트라로 쉽게 계산할 수 있다. 이제 가운데 $P_j$에서 시작한 최단 경로를 구해서, 각 $P_i, P_k$에 대해 구하면 되겠다. $O(V+E)$의 다익스트라를 $P \leq 100$번 돌려야 한다. 조금 무거운 4천만정도일거같은데, 6초제한이니 잘 돌것같다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M; cin >> N >> M; vector<vector<pll>> links(N+1); rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } int X, Z; cin >> X >> Z; vector<ll> dist_fromX(N+1, 1e18), dist_fromZ(N+1, 1e18); auto dijkstra = [&](ll start, vector<ll> &dist){ priority_queue<pll, vector<pll>, greater<pll>> pq; dist[start] = 0; pq.push({0, start}); while(!pq.empty()){ auto [cd, cur] = pq.top(); pq.pop(); if(cd > dist[cur]) continue; for(auto [nxt, w] : links[cur]){ ll nd = cd + w; if(nd < dist[nxt]){ dist[nxt] = nd; pq.push({nd, nxt}); } } } }; dijkstra(X, dist_fromX); dijkstra(Z, dist_fromZ); int P; cin >> P; vector<int> cand(P); rep(i, 0, P) cin >> cand[i]; ll ans = 1e18; for(int c2: cand){ vector<ll> dist_fromC(N+1, 1e18); dijkstra(c2, dist_fromC); for(int c1: cand) for(int c3: cand){ if(c1 == c2 || c2 == c3 || c1 == c3) continue; ans = min(ans, dist_fromX[c1] + dist_fromC[c1] + dist_fromC[c3] + dist_fromZ[c3]); } } if(ans >= 1e18) ans = -1; cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/21940 🧐 관찰 및 접근 # 일단 가중치가 있는 방향 그래프인데.. 어떤 도시 $X$에 대해 준형이와 친구들이 살고있는 모든 도시에 대해 왕복 시간을 구할 수 있을까? $N$이 충분히 작으므로, 플로이드 워셜을 사용해서 모든 도시간의 이동시간을 구할 수 있겠다. 이후에는 모든 도시 $X$에 대해 $K$번의 계산으로 왕복시간들의 최댓값을 구할 수 있다. 시간복잡도 $O(N^3 + NK)$로 풀릴 것 같다! 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; rep(i, 0, N) rep(j, 0, N) cost[i][j] = 1e15; rep(i, 0, N) cost[i][i] = 0; rep(i, 0, M){ int u, v, w; cin >> u >> v >> w; u--; v--; cost[u][v] = w; } rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]); cin >> K; vector<int> v(K), ans; rep(i, 0, K) cin >> v[i]; ll mn = 1e15; rep(X, 0, N){ ll tmp = 0; for(auto c: v) tmp = max(tmp, cost[X][c-1] + cost[c-1][X]); if(tmp < mn){ mn = tmp; ans.clear(); } if(tmp == mn) ans.push_back(X+1); } for(auto c: ans) cout << c << ' '; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1865 🧐 관찰 및 접근 # 무향인 도로와 유향인 웜홀이 있고, 음수 사이클이 있는지를 체크하는 문제이다. $N \leq 500$으로 크지 않으므로, 플로이드 워셜도 충분히 돈다. 이건 $O(N^3)$ 하지만 벨만포드로 $O(VE)$로 더 빠르게도 풀 수 있다. 벨만포드가 된다는건 SPFA로도 더 빠르게 풀 수 있다! 다 해본 결과, 플로이드워셜이 496ms, 벨만포드가 24ms, SPFA가 12ms가 나왔다. 💻 풀이 # 코드 (C++): void solve(){ int N, M, W; cin >> N >> M >> W; vector<vector<ll>> cost(N, vector<ll>(N, 1e15)); rep(i, 0, N) cost[i][i] = 0; rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; u--; v--; cost[u][v] = min(cost[u][v], w); cost[v][u] = min(cost[v][u], w); } rep(i, 0, W){ ll u, v, w; cin >> u >> v >> w; u--; v--; cost[u][v] = min(cost[u][v], -w); } rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]); rep(i, 0, N) if(cost[i][i] < 0){ cout << "YES\n"; return; } cout << "NO\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1504 🧐 관찰 및 접근 # $a$에서 $b$까지 가되, $v_1, v_2$를 무조건 지니야 한다. 이는 $a \rightarrow v_1 \rightarrow v_2 \rightarrow b$ 혹은 $a \rightarrow v_2 \rightarrow v_1 \rightarrow b$ 두가지중 하나이지 않을까? 각 움직임에 대해 나이브하게 다익스트라를 수행해도 6번밖에 안되므로, 그냥 돌리자. 경로가 없을 수 있음에 유의하자. 💻 풀이 # 코드 (C++): int N, E; vector<pii> links[810]; int get_dist(int s, int e){ vector<int> dist(N+1, 1e9); priority_queue<pii, vector<pii>, greater<pii>> pq; dist[s] = 0; pq.push({0, s}); while(!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); if(dist[u] < d) continue; if(u == e) return d; for(auto [v, w]: links[u]){ if(dist[v] > d+w){ dist[v] = d+w; pq.push({dist[v], v}); } } } return 1e8; } void solve(){ cin >> N >> E; rep(i, 0, E){ int u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } int v1, v2; cin >> v1 >> v2; int ans = min(get_dist(1, v1) + get_dist(v1, v2) + get_dist(v2, N), get_dist(1, v2) + get_dist(v2, v1) + get_dist(v1, N)); if(ans >= 1e8) cout << -1; else cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/24945 🧐 관찰 및 접근 # 서브태스크가 상당히 많고, 문제가 쉽지 않아보인다. 차근차근 해보자. $N = 3$ 브루트포스에 가깝게 풀 수 있을 것 같다. 문자는 어차피 최대 3개 존재하므로, 3개에 대해 $X$가 가질 수 있는 경우의 수 $3^3$가지, $Y$가 가질 수 있는 경우 $3^3$가지를 전이하면서 다익스트라로 풀 수 있을 것 같다. ㅇㅋ 된당 $S_i = a$ 모든 문자가 a라면? $X$에 들어있는 문자 개수, $Y$에 들어있는 문자 개수 두가지를 이용해서 $N^2$ 정점 다익스트라가 가능해보인다. $N \leq 30$ 이제부터 진짜로 어떻게풀어야하는지 고민해봐야할 것 같은데… 일단 복사할 문자 $Y$는 $X$의 substr이어야할 것이다. 그럼 $Y$가 될 수 있는 경우의수는 $O(N^2)$이고 $X$를 만들때든, $Y$를 만들기위해 빌드업하고 있을때든 결국 $X$도 $X$의 substr로 존재해야한다. 이것도 경우의수가 $O(N^2)$ 인 것 같다. $Y$를 붙일 수 있는지 검사하는? 그런것들이 전처리를 안하면 $O(N)$쯤 되어보이니, 아마 종합해서 $O(N^5)$정도로 풀 수 있지 않나? 근데 DP 전이식이 헷갈린다. 이게 상호 참조가 없나? 비용들이 달라서 다익으로 해야될 것 같은데. $\text{DP}[x][y]$: 현재 $X$에 $x$, $Y$에 $y$가 들어있다고 하자. $A$ 연산을 거치면 $x$에 한개가 붙고, $y$는 그대로다. $B$ 연산을 거치면 $x$가 빈 문자열이 되고, $y$는 $x$의 값으로 갱신된다. $C$연산을 거치면 $x = x + y$가 되고, $y$는 그대로다. 아하, 생각보다 $y$가 갱신될일이 없다. 그리고 $y$가 갱신된다면 $x$가 빈 문자열이 된 상태에서 시작한다! 복사하고 붙여넣는 과정을 그냥 해버렸다고 생각하는게 더 쉬울 것 같다. $\text{DP}[i][j]$ : $S_i$~$S_j$까지 만드는 최소비용이라고 하자. 이건 $\text{DP}[i][j-1]$ 후 $A$연산을 하거나 어떤 $i \leq i', j' \leq j$가 있어서 그친구를 복사한 후 붙여넣기를 여러번 하거나. 이건 그리디하게 되는듯? 한번 짜보자. 오!!! 이걸로 대충 $30^5$정도는 성공했다! $N \leq 200$ 이제 $O(N^4)$는 16억이니 빡세고, $O(N^3\log{N})$쯤 까지는 줄여야하는데… 섭태 5는 세제곱, 섭태 6은 제곱로그겠다. 음, 위에서 했던 관찰대로 $Y$에 복사해서 넣으면 $X$는 초기화돼서 시작하므로, DP를 $B$연산으로 $Y$에 복사한거까지 했을 때를 기준으로 하자. 젤 중요한거는 저 그리디하게 비교하면서 뒤로 슝슝슝 가는 파트인 것 같다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> S >> A >> B >> C; if(N >= mxN) { cout << -1 << "\n"; return; } rep(i, 0, N+1) rep(j, 0, N+1) DP[i][j] = LLONG_MAX; rep(i, 0, N+1) rep(j, i+1, N+1) DP[i][j] = A * (j-i) + B; const mint base = 131; const mint2 base2 = 137; vector<mint> hsh(N+1), pw(N+1); vector<mint2> hsh2(N+1), pw2(N+1); hsh[0] = 0; pw[0] = 1; hsh2[0] = 0; pw2[0] = 1; rep(i, 0, N){ hsh[i+1] = hsh[i] * base + S[i]; pw[i+1] = pw[i] * base; hsh2[i+1] = hsh2[i] * base2 + S[i]; pw2[i+1] = pw2[i] * base2; } auto getHash = [&](int l, int r) -> pair<ll, ll>{ ll ret1 = (hsh[r] - hsh[l] * pw[r-l]).get(); ll ret2 = (hsh2[r] - hsh2[l] * pw2[r-l]).get(); return {ret1, ret2}; }; ll ans = N*A; rep(L, 1, N+1){ // A 연산 앞뒤에 붙여서 전이할 때 if(L >= 2) rep(s, 0, N){ if(s+L > N) break; int e = s+L; DP[s][e] = min(DP[s][e], DP[s+1][e]+A); DP[s][e] = min(DP[s][e], DP[s][e-1]+A); } // 해당 문자열을 복사하는 최소 비용 map<pair<ll,ll>, vector<int>> mp; rep(s, 0, N){ if(s+L > N) break; int e = s+L; mp[getHash(s, e)].push_back(s); } // 복사 연산으로 전이 for(auto& [_, v]: mp){ int sz = v.size(); ll mn = 1e18; for(auto s: v) mn = min(mn, DP[s][s+L]); // 다음에 갈 수 있는 위치 vector<int> nxt(sz, sz); for(int i = 0, j = 0; i < sz; i++){ while(j < sz && v[j] < v[i]+L) j++; nxt[i] = j; } rep(i, 0, sz){ int s_pos = v[i]; int cidx = i; int cnt = 0; while(cidx < sz){ cnt++; int e_pos = v[cidx]+L; if(e_pos > N) break; DP[s_pos][e_pos] = min(DP[s_pos][e_pos], mn + (C * cnt) + ((e_pos - s_pos) - (L * cnt)) * A + B); cidx = nxt[cidx]; } } } } ans = min(ans, DP[0][N] - B); cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/27844 번역 문제 번역 # $N$개의 목초지가 있고 ($2 \le N \le 2\cdot 10^5$), $N-1$개의 도로로 연결되어 트리를 형성합니다. 모든 도로를 건너는 데 1초가 걸립니다. 각 목초지는 처음에 풀이 0개이고, $i$번째 목초지의 풀은 초당 $a_i$ ($1\le a_i\le 10^8$) 단위의 속도로 자랍니다. Farmer John은 처음에 목초지 1에 있으며, 모든 목초지의 풀에 비료를 주기 위해 돌아다녀야 합니다. 그가 $x$ 단위의 풀이 있는 목초지를 방문하면, $x$만큼의 비료가 필요합니다. 목초지는 처음 방문할 때만 비료를 주면 되고, 비료를 주는 데는 시간이 걸리지 않습니다.

w## 📝 문제 정보 링크: https://www.acmicpc.net/problem/10044 번역 문제 # JOI 군은 점심으로 중화요리집에서 샤오롱바오를 먹기로 했다. 샤오롱바오는 속재료와 뜨거운 국물을 밀가루 피로 싼 요리로, 먹을 때 국물이 주위로 튀는 것으로 알려져 있다. JOI 군이 주문한 샤오롱바오 세트는 속재료나 국물이 다른 N개의 샤오롱바오로 이루어져 있다. N개의 샤오롱바오는 등간격으로 일렬로 놓여 있으며, 순서대로 1부터 N까지 번호가 매겨져 있다. i번째 샤오롱바오와 j번째 샤오롱바오 사이의 거리는 절댓값 |i - j|이다.