코드 복사/붙여넣기 하는 당신이 아름답습니다.

2017 선린 봄맞이 교내대회 풀이

문제 링크: https://www.acmicpc.net/contest/view/222

뭔가 야심차게 HARD 난이도(교내대회 기준)로 낸 문제들이 여럿 있었는데

생각치 못하게 엄청 쉽게 풀려서 당황스러웠다 ㅠㅠ

A. 욱제는 효도쟁이야!!

14487 : 욱제는 효도쟁이야!!

풀이

각 마을간의 이동거리가 주어지고, 모든 마을을 순회할 때 그 이동거리의 합을 최소로 만드는 문제이다.

모든 이동거리의 합에서 최대 이동거리를 빼주면 된다.

코드

#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. 준오는 급식충이야!!

14488 : 준오는 급식충이야!!

풀이

원래 출제 의도는 만날 수 있는 시간을 이분탐색으로 찾도록 해서 꽤 난이도 있는 문제로 낸 건데

문제 내면서 조건에 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. 치킨 두 마리 (…)

14489 : 치킨 두 마리 (…)

풀이

단순 계산

코드

#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. 백대열

14490 : 백대열

풀이

최대공약수 구현을 테스트한 문제이다.

유클리드 호제법을 이용하면 빠르게 최대공약수를 구할 수 있다.

코드

#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진수

14491 : 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. 부울행렬의 부울곱

14492 : 부울행렬의 부울곱

풀이

수식이 주어졌을 때, 수식을 코드로 표현할 수 있는지 알아보자!

코드

#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. 과일노리

14493 : 과일노리

풀이

단순 구현 문제이다.

나머지 연산자를 이용하면 쉽게 구현할 수 있다.

코드

#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. 다이나믹이 뭐에요?

14494 : 다이나믹이 뭐에요?

풀이

다이나믹 프로그래밍에 대한 교육 목적의 문제이다.

간단한 점화식을 세워서 문제를 해결할 수 있다.

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. 피보나치 비스무리한 수열

14495 : 피보나치 비스무리한 수열

풀이

피보나치 수열을 약간 변형했다.

이것도 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. 그대, 그머가 되어

14496 : 그대, 그머가 되어

풀이

문자를 노드로 생각하고, 치환 가능한 문자쌍에 간선을 이어주자.

모든 가중치가 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. 주난의 난(難)

14497 : 주난의 난(難)

풀이

원래는 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. 학급비 낭비하기

14498 : 학급비 낭비하기

풀이

올솔브 방지용 문제!

문제를 그래프화 시켜보자.

뽁뽁이 구매 희망을 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;
}
wookje.kwon's profile image

wookje.kwon

2017-04-09 19:00

Read more posts by this author