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

A. 비밀번호

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

#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꼴이여야 홀수개의 약수를 갖게되고 이는 곧 열려있는 창문 수가 된다.

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

C. 개업

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

#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다. 단순 구현이라고 생각하면 좋을 것 같다.

#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. 과제

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

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

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

#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 돌리는 중에 계산한다면 상관이 없다만, 나처럼 소스를 구성한다면 범위에 신경써줘야한다.

#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번 계산하게 된다.

#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 변형해서 풀어야 할듯.