2016년 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회

문제 링크

E. 닉네임에 갓 붙이기

$N$개의 닉네임이 음절 단위로 쪼개져 주어진다. 첫 음절을 제외하고, 맨 앞에 "god"을 붙여 출력하는 문제다.

줄 별로 입력받고 입력 받은 문자열을 공백으로 나누어 문자열 배열로 만들어주면 된다. C, C++에서 이는 strtok 함수를 통해 간단히 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; int T; char buf[999]; int main() { for (scanf("%d ", &T);T--;){ fgets(buf, 997, stdin); bool sw = 0; printf("god"); for (char *pt=strtok(buf, " \n\r");pt;pt=strtok(0, " \n\r")){ if (sw) printf(pt); sw = 1; } puts(""); } }

F. 행복 유치원

오름차순으로 정렬된 길이 $N$인 배열이 주어진다. 이 배열을 $K$개의 파티션으로 나누는데 각 파티션에 해당하는 비용은 최대값-최소값이다. 이 때 $K$개의 파티션으로 나누었을 때 최소 비용을 구하는 문제다.

배열 $[1, 3, 4, 8, 10]$을 $[1]$, $[3, 4]$, $[8, 10]$ 세 개의 파티션으로 나누었을 때 비용은 (10 - 1) - (3 - 1) - (8 - 4) = 3이 된다. 즉, 배열이 정렬되어있으므로 인접한 두 값의 차이를 내림차순으로 정렬한 뒤 상위 $K-1$개의 값을 (전체 최대값 - 전체 최소값)에서 빼주면 답이 된다.

#include <bits/stdc++.h> using namespace std; #define MAXN 300005 #define pb push_back #define all(v) (v).begin(), (v).end() int N, K; int A[MAXN]; int main() { scanf("%d%d", &N, &K); for (int i=1;i<=N;i++) scanf("%d", A+i); int ans = A[N] - A[1]; vector <int> arr; for (int i=1;i<N;i++) arr.pb(A[i+1] - A[i]); sort(all(arr), greater<int>()); for (int i=0;i<K-1;i++) ans -= arr[i]; printf("%d\n", ans); }

L. 떨어진 수정

강도가 $P$이하의 양의 실수로 표현되는 마나 수정 $N$개가 있다. 망치를 휘둘러 $P$이하의 강도로 마나 수정을 내리치는데, 마나 수정의 강도보다 $W$이상 강한 힘으로 내리치면 수정이 폭발하고 그보다 적은 마나 수정의 강도 이상의 힘으로 내리치면 파괴된다. 이 중 $K$번째로 강도가 쎈 마나 수정을 폭발이 아닌 파괴를 시키기 위해 최악의 경우 필요한 내리치는 회수의 최소값을 구하는 문제다.

풀이에 비해 문제 설명이 매우 복잡하다(...) 결론부터 말하면 답은 $\lceil \frac{P}{W} \rceil$ 이다. 내리치는 강도를 $W, 2W, \dots, P$로 하는 것이 최악의 경우 회수를 최소화하는 최적의 방법이다.

#include <bits/stdc++.h> using namespace std; int P, W; int main() { scanf("%*d%*d%d%d", &P, &W); printf("%d\n", (P-1)/W+1); }

J. 내일로 여행

$N$개의 도시가 있고, $K$개의 교통 수단이 있다. 도시들을 주어진 순서대로 여행하는데, 내일로 티켓을 사면 특정 교통 수단의 비용이 감소한다. 이 때, 내일로 티켓을 사는 것이 이득인지 판단하는 문제다.

$N \leq 100$이므로 Floyd-Warshall 알고리즘을 이용해 모든 두 도시 쌍 사이를 이동하는 최단 거리를 구하는 것이 편하다. 이 때, 내일로 티켓을 사는 경우와 사지 않는 경우에 대한 인접행렬을 따로 만들어 계산하면 된다. 내일로 티켓을 살 경우 "S-Train"과 "V-Train"은 비용이 절감되므로 전체 비용 스케일을 두 배로 늘려 실수 연산을 피할 수 있다. (시간 테스트 용도로 이 문제 코드는 Java로 작성되었음)

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); HashMap <String, Integer> num = new HashMap<String, Integer>(); int N = sc.nextInt(); int R = sc.nextInt(); for (int i=0;i<N;i++){ String s = sc.next(); num.put(s, i); } int M = sc.nextInt(); int[] arr = new int[M]; for (int i=0;i<M;i++){ String s = sc.next(); arr[i] = num.get(s); } int K = sc.nextInt(); int[][] w1 = new int[N][N]; int[][] w2 = new int[N][N]; for (int i=0;i<N;i++) for (int j=0;j<N;j++) w1[i][j] = w2[i][j] = (i == j ? 0 : (int)1e9); for (int i=0;i<K;i++){ String a = sc.next(); String b = sc.next(); String c = sc.next(); int d = sc.nextInt(); d <<= 1; int p = num.get(b), q = num.get(c); w1[p][q] = Math.min(w1[p][q], d); w1[q][p] = w1[p][q]; if (a.equals("Mugunghwa") || a.equals("ITX-Saemaeul") || a.equals("ITX-Cheongchun")) d = 0; if (a.equals("S-Train") || a.equals("V-Train")) d >>= 1; w2[p][q] = Math.min(w2[p][q], d); w2[q][p] = w2[p][q]; } for (int k=0;k<N;k++) for (int i=0;i<N;i++) for (int j=0;j<N;j++){ w1[i][j] = Math.min(w1[i][j], w1[i][k]+w1[k][j]); w2[i][j] = Math.min(w2[i][j], w2[i][k]+w2[k][j]); } int v1 = 0, v2 = R+R; for (int i=1;i<M;i++){ v1 += w1[arr[i-1]][arr[i]]; v2 += w2[arr[i-1]][arr[i]]; } System.out.println(v2 < v1 ? "Yes" : "No"); } }

B. 최대 클리크 구하기

$N$개의 정점이 있는 구간 그래프가 주어졌을 때, 최대 클리크를 구하는 문제다.

구간 그래프에서 클리크는 구간들을 아래 그림처럼 나타내었을 때, 구간들을 관통하는 수직선 하나로 볼 수 있다.

때문에 최대 클리크는 가장 많은 구간을 관통하는 수직선을 찾고 그 수직선이 관통하는 구간들을 찾는 것으로 구할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 300005 #define pb push_back #define sz(v) ((int)(v).size()) int N; struct Z{ int s, e, idx; } A[MAXN]; int main() { scanf("%d", &N); for (int i=1;i<=N;i++){ scanf("%d%d", &A[i].s, &A[i].e); A[i].idx = i; } sort(A+1, A+N+1, [](const Z &a, const Z &b){ return a.s < b.s; }); priority_queue <int> que; int ans = 0, mx_x = 0; for (int i=1;i<=N;i++){ while (!que.empty() && -que.top() < A[i].s) que.pop(); que.push(-A[i].e); if (ans < sz(que)) ans = sz(que), mx_x = A[i].s; } vector <int> path; for (int i=1;i<=N;i++){ if (A[i].s <= mx_x && mx_x <= A[i].e) path.pb(A[i].idx); } printf("%d\n", ans); for (int t: path) printf("%d ", t); puts(""); }

H. 범죄 파티

이분탐색으로 파티의 비용을 정하고, 정한 파티 비용으로 모든 용의자가 적어도 한 명의 변호인을 둘 수 있는지 확인하는 결정 문제를 해결한다. 결정 문제는 2-SAT 혹은 이분매칭으로 해결할 수 있다. $N \leq 200,000$으로 굉장히 커서 이분매칭으로 안될 것 같아보이지만, 이 문제에서 이분그래프 간선의 수가 최대 $2N$이므로 Hopcroft-Karp 알고리즘으로 $O(N^{1.5})$으로 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back typedef pair<int, int> pii; int N, M; int dist[MAXN], match[MAXN*2]; bool used[MAXN]; vector <pii> ocon[MAXN]; vector <int> con[MAXN]; void bfs() { for (int i=1;i<=N;i++) dist[i] = 1e9; queue <int> que; for (int i=1;i<=N;i++) if (!used[i]) dist[i] = 0, que.push(i); while (!que.empty()){ int q = que.front(); que.pop(); for (int t: con[q]){ int m = match[t]; if (m && dist[m] == 1e9) dist[m] = dist[q]+1, que.push(m); } } } bool dfs(int n) { for (int t: con[n]){ int m = match[t]; if (!m || dist[m] == dist[n]+1 && dfs(m)){ used[n] = 1; match[t] = n; return 1; } } dist[n] = 1e9; return 0; } bool proc(int m) { for (int i=1;i<=N;i++){ con[i].clear(); for (pii &p: ocon[i]) if (p.second <= m) con[i].pb(p.first); } for (int i=1;i<=N;i++) used[i] = 0; for (int i=1;i<=M;i++) match[i] = 0; int ans = 0; for (int flow=1;flow;){ bfs(); flow = 0; for (int i=1;i<=N;i++) if (!used[i] && dfs(i)) flow++; ans += flow; } return ans == N; } int main() { scanf("%d", &N); M = N+N; for (int i=1;i<=N;i++){ for (int j=2;j--;){ int t, v; scanf("%d%d", &t, &v); ocon[i].pb({t, v}); } } int s = 0, e = 1e6, ans = -1; while (s <= e){ int m = s+e>>1; if (proc(m)) e = m-1, ans = m; else s = m+1; } printf("%d\n", ans); }