2016 홍익대학교 프로그래밍 경진대회

A. Hawk eyes

모든 경우에 대해 switch~case 문으로 값을 변경해주는 것으로 구성하면 된다. 마지막엔 순회하여 위치값을 출력해준다.

#include <cstdio>
#include <algorithm>
int main() {
	char S[201];
	int cup[4] = { 1,0,0,2 },i;
	scanf("%s", S);
	for (i = 0; S[i]; i++) {
		switch (S[i]) {
		case 'A': std::swap(cup[0], cup[1]); break;
		case 'B': std::swap(cup[0], cup[2]); break;
		case 'C': std::swap(cup[0], cup[3]); break;
		case 'D': std::swap(cup[1], cup[2]); break;
		case 'E': std::swap(cup[1], cup[3]); break;
		case 'F': std::swap(cup[2], cup[3]); break;
		}
	}
	for (i = 0; i < 4; i++) if (cup[i] == 1) printf("%d\n", i + 1);
	for (i = 0; i < 4; i++) if (cup[i] == 2) printf("%d", i + 1);
	return 0;
}

 

B. 점화식

주어진 점화식이 이미 있으니 다이나믹으로 해결한다. 재귀 dp를 써도 좋고 순회 dp를 써도 좋다.

#include <cstdio>
int main() {
	long long dp[40] = {1}, i, n,j;
	scanf("%lld", &n);
	for (i = 1; i <= n; i++)
		for (j = 0; j < i; j++)
			dp[i] += dp[j] * dp[i - j - 1];
	printf("%lld", dp[n]);
	return 0;
}

C. 완전 범죄

BFS이긴 한데, 다소 디스크립션이 애매한 문제였다. 가령 앞으로 가는 키를 눌렀을 땐 정확히 그 칸만큼 앞으로 가야하고, 갈 수 없을 땐 그 앞에서 멈추는 경우는 없는 식이다. 나머지는 BFS라서 간단하겠다.

#include <cstdio>
#include <queue>
using namespace std;
int main() {
	int check[100001] = {};
	int N, S, D, F, B, K, u,k;
	scanf("%d%d%d%d%d%d", &N, &S, &D, &F, &B, &K);
	queue<int> q;
	q.push(S);
	check[S] = 1;
	while (K--) {
		scanf("%d", &k);
		check[k] = 1;
	}
	while (!q.empty()) {
		u = q.front(); q.pop();
		if (1 <= u - B && !check[u - B]) {
			check[u - B] = check[u] + 1;
			q.push(u - B);
		}
		if (u + F <= N && !check[u + F]) {
			check[u + F] = check[u] + 1;
			q.push(u + F);
		}
	}
	if (check[D]) printf("%d", check[D] - 1);
	else printf("BUG FOUND");

	return 0;
}

D. 중복 제거

시간과 메모리 측면을 묻는 문제다. 숫자가 int형 범위 안에 들어오고, 배열로 표현할 수 있으니 본인은 해싱을 이용하여 해결했다. map을 사용하면 N^2lgN으로 찾지 못할것 같았다.

#include <cstdio>
int main() {
	int c[1 << 20] = {},d,divi=1<<5;
	while (~scanf("%d", &d)) {
		if (!((c[d / divi] >> (d%divi)) & 1)) {
			c[d / divi] += 1 << (d%divi);
			printf("%d ", d);
		}
	}
	return 0;
}

E. 이상한 술집

너무나도 명백한 이분탐색 문제다. 비슷한 문제를 추천한다.

https://www.acmicpc.net/problem/2805

https://www.acmicpc.net/problem/1654

#include <cstdio>
int max_v(int a, int b) { return a > b ? a : b; }
int main() {
	int N, K,*mak,i,sum,ans=1;
	long long left = 1, right = 0, mid;
	scanf("%d%d", &N, &K);
	mak = new int[N];
	for (i = 0; i < N; i++) {
		scanf("%d", &mak[i]);
		right = max_v(right, mak[i]);
	}
	while (left <= right) {
		mid = (left + right) / 2;
		sum = 0;
		for (i = 0; i < N; i++)
			sum += mak[i] / mid;
		if (sum >= K) {
			ans = mid;
			left = mid + 1;
		}
		else right = mid - 1;
	}
	printf("%d", ans);

	return 0;
}

F. 물벼룩의 생존확률

경우의 수 DP를 이용한다. 수면과 수면 아래를 적절하게 배열값으로 표현한다.

경우의 수가 int 형 범위를 넘길 수 있기 때문에 long long으로 처리해주자.

#include <cstdio>
#include <cstring>
int n, surface = 128;
long long cache[65][260];
long long rec(int sec, int pos) {
	if (sec == n) return pos < surface ? 1 : 0;
	if (pos >= surface) return 0;
	long long& ret = cache[sec][pos];
	if (ret == -1) ret = rec(sec + 1, pos - 1) + rec(sec + 1, pos + 1);
	return ret;
}
int main() {
	memset(cache, -1, sizeof(cache));
	int k;
	scanf("%d%d", &k, &n);
	printf("%lld", rec(0, surface-k));
	return 0;
}