2017 선린 봄맞이 교내대회 풀이
문제 링크: https://www.acmicpc.net/contest/view/222
뭔가 야심차게 HARD 난이도(교내대회 기준)로 낸 문제들이 여럿 있었는데
생각치 못하게 엄청 쉽게 풀려서 당황스러웠다 ㅠㅠ
A. 욱제는 효도쟁이야!!
풀이
각 마을간의 이동거리가 주어지고, 모든 마을을 순회할 때 그 이동거리의 합을 최소로 만드는 문제이다.
모든 이동거리의 합에서 최대 이동거리를 빼주면 된다.
코드
#include <stdio.h>
int n, tmp, sum, i, a;
int main() {
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &a);
if (tmp < a) tmp = a;
sum += a;
}
printf("%d", sum - tmp);
return 0;
}
B. 준오는 급식충이야!!
풀이
원래 출제 의도는 만날 수 있는 시간을 이분탐색으로 찾도록 해서 꽤 난이도 있는 문제로 낸 건데
문제 내면서 조건에 T를 넣어버리는 바람에 선형으로도 풀리게 되었다 ㅠㅠ
아무튼 각각의 좌표 x[i]를 돌면서 T동안 v[i]를 달려서 갈 수 있는 max_left, min_right를 구한다.
max_left < min_right면 만날 수 있다.
코드
아래는 dotorya님의 코드. 코드 사용을 허락해주신 dotorya님 감사합니다!
#include <stdio.h>
#include <algorithm>
using namespace std;
#define ldb ldouble
typedef long long ll;
typedef double db;
const ll LL_INF = 1234567890123456789ll;
int x[50050], v[50050];
int main() {
int N, i;
db mn = -LL_INF, mx = LL_INF, T;
scanf("%d", &N);
scanf("%lf", &T);
for (i = 1; i <= N; i++) scanf("%d", &x[i]);
for (i = 1; i <= N; i++) scanf("%d", &v[i]);
for (i = 1; i <= N; i++) {
mn = max(mn, x[i] - v[i] * T);
mx = min(mx, x[i] + v[i] * T);
}
if (mn < mx + 1e-08) printf("1\n");
else printf("0\n");
return 0;
}
C. 치킨 두 마리 (…)
풀이
단순 계산
코드
#include <stdio.h>
int main() {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if (c * 2 > a + b) printf("%d", a + b);
else printf("%d", a + b - c * 2);
return 0;
}
D. 백대열
풀이
최대공약수 구현을 테스트한 문제이다.
유클리드 호제법을 이용하면 빠르게 최대공약수를 구할 수 있다.
코드
#include <cstdio>
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
int a, b, c;
scanf("%d:%d", &a, &b);
c = gcd(a, b);
printf("%d:%d", a / c, b / c);
return 0;
}
E. 9진수
풀이
10진수를 9진수로 변환한다.
코드
#include <cstdio>
int n, b;
void f(int x, int p) {
if (x) {
f(x / 9, p);
putchar('0'+x%p);
}
}
int main() {
scanf("%d", &n);
f(n, 9);
return 0;
}
F. 부울행렬의 부울곱
풀이
수식이 주어졌을 때, 수식을 코드로 표현할 수 있는지 알아보자!
코드
#include <stdio.h>
int n, ans;
int a[303][303], b[303][303], c[303][303];
int main() {
int i, j, k;
scanf("%d", &n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &a[i][j]);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &b[i][j]);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
for (k = 0; k < n; k++)
c[i][j] |= (a[i][k] & b[k][j]);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (c[i][j]) ans++;
printf("%d", ans);
return 0;
}
G. 과일노리
풀이
단순 구현 문제이다.
나머지 연산자를 이용하면 쉽게 구현할 수 있다.
코드
#include <stdio.h>
int n, adj, len, cnt, now;
int main() {
int i;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d %d", &adj, &len);
now = cnt % (adj + len);
if (now < len) cnt += len - now;
cnt += 1;
}
printf("%d", cnt);
return 0;
}
H. 다이나믹이 뭐에요?
풀이
다이나믹 프로그래밍에 대한 교육 목적의 문제이다.
간단한 점화식을 세워서 문제를 해결할 수 있다.
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]
코드
#include <stdio.h>
const int mod = 1e9 + 7;
int n, m, dp[1001][1001];
int main() {
scanf("%d %d", &n, &m);
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = ((long long)dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
}
}
printf("%d", dp[n][m]);
return 0;
}
I. 피보나치 비스무리한 수열
풀이
피보나치 수열을 약간 변형했다.
이것도 H와 같은 동적 계획법 문제이다.
점화식이 주어져 있으므로 그대로 구현하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long a[130]={0,1,1,1};
scanf("%d",&n);
for(int i=4;i<=n;i++) {
a[i] = a[i-1] + a[i-3];
}
printf("%lld",a[n]);
return 0;
}
J. 그대, 그머가 되어
풀이
문자를 노드로 생각하고, 치환 가능한 문자쌍에 간선을 이어주자.
모든 가중치가 1인 그래프에서 a->b의 최단경로를 찾는 문제로 바뀐다.
dfs, bfs 등 자유롭게 구현하면 된다.
코드
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int n_ = 1e3 + 10;
int n, m, s, t;
int dst[n_];
vector<int> gph[n_];
int main() {
scanf("%d %d %d %d", &s, &t, &n, &m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
gph[a].push_back(b);
gph[b].push_back(a);
}
memset(dst, -1, sizeof(dst));
queue<pair<int, int> > que;
dst[s] = 0;
que.push({ s,0 });
while (!que.empty()) {
auto now = que.front();
que.pop();
for (auto nxt : gph[now.first]) {
if (dst[nxt] > now.second + 1 || dst[nxt] == -1) {
dst[nxt] = now.second + 1;
que.push({ nxt,now.second + 1 });
}
}
}
printf("%d", dst[t]);
return 0;
}
K. 주난의 난(難)
풀이
원래는 flood fill 문제인데…
너무 빨리 풀리길래 제출 코드를 읽어봤다.
단순한 탐색으로 풀린다는 사실을 깨달았다 ㅠㅠ
아래는 flood fill 풀이이다.
코드
#include <bits/stdc++.h>
#define y1 WhoDefinedFuckingY1FunctionAtMathHeader
using namespace std;
const int dx[] = { 0,0,-1,1 };
const int dy[] = { -1,1,0,0 };
int n, m, x1, y1, x2, y2, cnt;
int chk[303][303];
char a[303][303];
struct pos { int x, y; };
int main() {
int i, j;
scanf("%d %d", &n, &m);
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
--x1, --y1, --x2, --y2;
for (i = 0; i < n; i++) scanf("%s", a[i]);
queue<pos> que, tmp;
que.push({ x1,y1 });
while (a[x2][y2] != '0') {
tmp.push({ x1,y1 });
cnt++;
que = tmp;
while (!tmp.empty()) tmp.pop();
while (!que.empty()) {
pos now = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
int nx = now.x + dx[i], ny = now.y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (a[nx][ny] == '0' && chk[nx][ny] == 0) {
que.push({ nx, ny });
}
else if (a[nx][ny] != '0') {
a[nx][ny] = '0';
tmp.push({ nx, ny });
}
chk[nx][ny] = cnt;
}
}
}
printf("%d", cnt);
return 0;
}
L. 학급비 낭비하기
풀이
올솔브 방지용 문제!
문제를 그래프화 시켜보자.
뽁뽁이 구매 희망을 A, 꼭꼭이 구매 희망을 B 집단으로 둔다.
학생들은 무조건 한 집단을 구매하길 원하고, 반대 집단을 구해하지 않길 원한다.
따라서 같은 집단을 구매하길 원하는 학생들끼리는 의견이 충돌할 일이 없다.
의견이 충돌하는 학생들끼리 간선을 이어주자.
결국 이분매칭 문제가 되었다.
코드
#include <bits/stdc++.h>
using namespace std;
const int k_ = 512 + 3;
vector<int> gph[k_];
int v1[k_], v2[k_], v3[k_], vst[k_];
bool chk[k_];
int matching(int u) {
for (auto v : gph[u]) {
if (chk[v]) continue;
chk[v] = true;
if (vst[v] == -1 || matching(vst[v])) {
vst[v] = u;
return true;
}
}
return false;
}
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
memset(vst, -1, sizeof(vst));
for (int i = 0; i < k; ++i) {
scanf("%d %d %d", &v1[i], &v2[i], &v3[i]);
}
for (int i = 0; i < k - 1; ++i) {
for (int j = i + 1; j < k; ++j) {
if ((v1[i] == v1[j] || v2[i] == v2[j]) && (v3[i] ^ v3[j])) {
if (v3[i] == 0) gph[i].push_back(j);
else gph[j].push_back(i);
}
}
}
int sum = 0;
for (int i = 0; i < k; ++i) {
memset(chk, 0, sizeof(chk));
if (matching(i)) ++sum;
}
printf("%d", sum);
return 0;
}