제 12회 총장배 서강대학교 프로그래밍 대회 Master (Ongoing)

A. 비밀번호

  재귀 완전탐색을 구현한다. 모든 가능한 숫자에 대해서 사용했으면 1을 추가해준다. 매우 간단.

?

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

#include <cstdio> int ans,n,m, used[10], mc[10]; void back(int p) {     if (p >= n + 1) {         bool f = 1;         for (int i = 0; i < m && f; i++)             if (!used[mc[i]]) f = 0;         ans += f;         return;     }     for (int i = 0; i < 10; i++) {         used[i]++;         back(p + 1);         used[i]--;     } } int main() {     scanf("%d%d", &n, &m);     for (int i = 0; i < m; i++)         scanf("%d", &mc[i]);     back(1);     printf("%d", ans);     return 0; }

B. 창문 닫기

  약수에 대해서 생각해보자. 숫자 6의 경우 1,2,3,6으로 총 2번 열닫했으므로 6번 창문은 닫혀있게된다.

  9의 경우 1,3,9로 열닫열 했으므로 열려있게 된다. 따라서 열려있기 위해서는 k^2꼴이여야 홀수개의 약수를 갖게되고 이는 곧 열려있는 창문 수가 된다.

?

1 2 3 4 5 6 7 8

#include <cstdio> #include <cmath> int main() {     int N;     scanf("%d", &N);     printf("%d", (int)sqrt(N));     return 0; }

C. 개업

  제 12회 총장배 서강대학교 프로그래밍 대회 Champion 참고

?

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 31 32 33

#include <cstdio> #include <unordered_set> using namespace std; int min_v(int a, int b) { return a < b ? a : b; } int main() {     int N, M, *dp, *s, i, j, off;     scanf("%d%d", &N, &M);     dp = new int[N + 1]{};     s = new int[M];     unordered_set<int> ables;     for (i = 0; i < M; i++) {         scanf("%d", &s[i]);         ables.insert(s[i]);         if (s[i] <= N) dp[s[i]] = 1;         for (j = 0; j<i; j++)             if (s[i] + s[j] <= N) {                 dp[s[i] + s[j]] = 1;                 ables.insert(s[i] + s[j]);             }     }       for (i = 1; i <= N; i++)         if (!dp[i]) {             dp[i] = 1e9;             for (auto it = ables.begin(); it != ables.end(); it++) {                 off = *it;                 if (1 <= i - off && dp[i - off] != 0)                     dp[i] = min_v(dp[i], dp[i - off] + 1);             }         }     printf("%d", dp[N] != 1e9 ? dp[N] : -1);     return 0; }

D. 출근

  1. 시작점은 첫행 모두다.

  2. 방향이 테케마다 다르다.

  위 두 개를 제외하면 그냥 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 31 32 33 34 35 36 37

#include <cstdio> #include <queue> using namespace std; int min_v(int a, int b) { return a < b ? a : b; } struct _d { int y, x; }; int main() {     bool board[1000][1000];     int R, C, N, *dy, *dx, i, j, vi[1000][1000] = {};     scanf("%d%d", &R, &C);     for (i = 0; i < R; i++) for (j = 0; j < C; j++)         scanf("%d", &board[i][j]);     scanf("%d", &N);     dy = new int[N], dx = new int[N];     for (i = 0; i < N; i++)         scanf("%d%d", &dy[i], &dx[i]);     queue<_d> q;     for (j = 0; j < C; j++)         if (board[0][j]) {             q.push(_d{ 0,j });             vi[0][j] = 1;         }     while (!q.empty()) {         _d u = q.front(); q.pop();         for (i = 0; i < N; i++) {             int ty = u.y + dy[i], tx = u.x + dx[i];             if (0 <= ty && ty < R && 0 <= tx && tx < C && board[ty][tx] && !vi[ty][tx]) {                 vi[ty][tx] = vi[u.y][u.x] + 1;                 q.push(_d{ ty,tx });             }         }     }     int ans = 1e9;     for (j = 0; j < C; j++)         ans = min_v(ans, vi[R - 1][j] == 0 ? 1e9 : vi[R - 1][j]);     printf("%d", ans == 1e9 ? -1 : ans - 1);     return 0; }

E. 과제

  하루에 한 과제를 할 수 있다는 점을 이용한다. 먼저 마감의 날짜로 오름차순 정렬을 한다.

  정렬된 것을 쭉 순회하며 마감날짜가 같은 날짜에 대해서 (현재 한 일 개수) > 마감날짜라면 하나를 삭제해준다. 삭제해주는

원리는 가장 가격이 낮은 것을 삭제해주도록 한다.

?

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

#include <cstdio> #include <algorithm> #include <queue> using namespace std;   int main() {     int n, i, ans = 0;     pair<int, int> a[1000];     scanf("%d", &n);     for (i = 0; i < n; i++) scanf("%d%d", &a[i].first, &a[i].second);     sort(a, a + n);     priority_queue<int> pq;     for (i = 0; i < n; i++) {         ans += a[i].second;         pq.push(-a[i].second);         if (pq.size() > a[i].first) ans += pq.top(), pq.pop();     }     printf("%d", ans);     return 0; }

F. 집 구하기

  시작점은 맥도날드, 스타벅스 따로 계산한다.

  그 다음 각각 Dijkstra를 돌린다. 그리고 한계 x,y에 대해 둘 다 만족하는 것 중 가장 작은 것을 답으로 낸다.

  주의할 점이 있다면, 거리값이 int 범위를 넘어갈 수도 있다는 점이다. Dijkstra 돌리는 중에 계산한다면 상관이 없다만, 나처럼 소스를 구성한다면 범위에 신경써줘야한다.

?

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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include <cstdio> #include <queue> #include <vector> #include <cstring> using namespace std; using ll = long long; const int MAX_V = 10000; struct _d { int v; ll w; }; ll min_v(ll a, ll b) { return a < b ? a : b; } vector<vector<_d>> adj; bool vi[MAX_V]; void dijkstra(ll dist[], priority_queue<pair<ll,int>>& pq) {     memset(vi, 0, sizeof(vi));     while (!pq.empty()) {         int u = pq.top().second; pq.pop();         if (vi[u]) continue;         vi[u] = 1;         for(_d& e : adj[u])             if (dist[e.v] > dist[u] + e.w) {                 dist[e.v] = dist[u] + e.w;                 pq.push(make_pair(-dist[e.v], e.v));             }     } }   int main() {     int V, E, u, v, w, i,M, x, S, y;     ll distM[MAX_V], distS[MAX_V], ans;     scanf("%d%d", &V, &E);     adj.resize(V);     while (E--) {         scanf("%d%d%d", &u, &v, &w);         u--, v--;         adj[u].push_back(_d{ v,w });         adj[v].push_back(_d{ u,w });     }     memset(distM, 0x7F, sizeof(distM));     memset(distS, 0x7F, sizeof(distS));     priority_queue<pair<ll, int>> pqM, pqS;     scanf("%d%d", &M, &x);     while (M--) {         scanf("%d", &u); u--;         distM[u] = 0;         pqM.push(make_pair(0, u));     }     scanf("%d%d", &S, &y);     while (S--) {         scanf("%d", &u); u--;         distS[u] = 0;         pqS.push(make_pair(0, u));     }     dijkstra(distM, pqM);     dijkstra(distS, pqS);     ans = 1e15;     for(i=0;i<V;i++)         if (0 < distM[i] && distM[i] <= x && 0 < distS[i] && distS[i] <= y)             ans = min_v(ans, distM[i] + distS[i]);     printf("%lld", ans == 1e15 ? -1 : ans);     return 0; }

G. 외계 생물

  

  포화 이진트리에서 높이가 h인 노드에 대해서 가능한 조합을 생각해보면, 우선 그 자식에 있는 수는 2^(h+1)-1개가 된다. 보통 글에서 나온 것처럼 포화 이진트리는 2^(h+1)-1개 이므로 최상위 노드 1개를 제외하면 2^(h+1)-2개가 아래에 존재하게 된다. 따라서 자식에 숫자를 할당하는 방법은 조합 (자식의 수)C(자식의 수/2)가 된다. 이유는 자식의 수에 할당할 번호를 a부터 b라고 하면, 여기서 반개를 뽑으면 나머지 반은 저절로 다른 자식으로 할당하게 되고, 이 뽑은 조합대로 알맞게 자식에 번호를 할당하는 경우의 수가 된다.

  여기서 할당된 자식에 대해서도 조합수를 계산해야하므로 h-1에 대해서 2번 계산하게 된다.

?

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

#include <cstdio> using ll = long long; const ll MOD = 1000000007LL;   int bi[2050][2050], cache[11] = { 1 }; void binormial() {     bi[0][0] = 1;     for (int i = 1; i < 2050; i++) {         bi[i][0] = 1;         for (int j = 1; j <= i; j++)             bi[i][j] = (bi[i - 1][j - 1] + bi[i - 1][j]) % MOD;     } }   int rec(int h) {     int& ret = cache[h];     if (!ret)         ret = (1LL*rec(h - 1)*rec(h - 1)) % MOD*bi[(1 << h + 1) - 2][(1 << h) - 1] % MOD;     return ret; }   int main() {     int H, half, T;     ll ans = 1;     scanf("%d", &H);     binormial();     printf("%d", rec(H));     return 0; }

H. 세금

TLE 받음 ㅠ, 두 가지 방식 둘다 .. Dijkstra 변형해서 풀어야 할듯.