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

A. Hawk eyes

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#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를 써도 좋다.

?

1 2 3 4 5 6 7 8 9 10

#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라서 간단하겠다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#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으로 찾지 못할것 같았다.

?

1 2 3 4 5 6 7 8 9 10 11

#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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#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으로 처리해주자.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#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; }