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

 A. 순서쌍의 곱의 합

  단순 for 두번 O(N^2)으로는 시간초과가 나버린다.

  구하는 것은 

(A1*A2 + A1*A3 + ... + A1*AN) + (A2*A3 + A2*A4 + ... A2*AN) + ... + (AN-1*AN) 꼴이 된다.

  규칙성을 말하자면 A1의 경우 A2부터 AN까지의 합에 곱셈을 해야하고,

  AK의 경우(1<= K< N) AK+1부터 AN까지의 합에 곱을 해야한다.

  따라서 O(N)으로 해결 가능하다.

#include <cstdio>
int main() {
	long long S = 0,R=0;
	int N, i,D,A[100001];
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &A[i]);
		S += A[i];
	}
	for (i = 0; i < N; i++) {
		S -= A[i];
		R += S*A[i];
	}
	printf("%lld", R);
	return 0;
}

 

 B. 로봇

  음.. 설명할게 없다. 그냥 문제 내용에 있는 것 그대로 구현을 한다.

  단지 방향성에 대해서 잘 처리해주면 코드를 다소 깔끔하게 작성할 수 있다.

#include <cstdio>
int main() {
	int R, C, dy[] = { -1,1,0,0 }, dx[] = { 0,0,-1,1 },ty,tx,y,x,k,seq[4],sp=0,chk[4],i;//상하좌우
	bool vi[1000][1000] = {}, moved;
	scanf("%d%d%d", &R, &C, &k);
	while (k--) {
		scanf("%d%d", &y, &x);
		vi[y][x] = 1;
	}
	scanf("%d%d", &y, &x);
	for (i = 0; i < 4; i++) {
		scanf("%d", &seq[i]);
		seq[i] -= 1;
	}
	vi[y][x] = 1;
	while (1) {
		for (i = 0; i < 4; i++) chk[i] = 0;
		while (1) {
			ty = y + dy[seq[sp]], tx = x + dx[seq[sp]];
			if (0 <= ty && ty < R && 0 <= tx && tx < C && !vi[ty][tx]) {
				y = ty, x = tx;
				vi[y][x] = 1;
			}
			else break;
		}
		moved = 0;
		for (i = 0; i < 4; i++) {
			ty = y + dy[seq[i]], tx = x + dx[seq[i]];
			if (0 <= ty && ty < R && 0 <= tx && tx < C && !vi[ty][tx])
				moved = 1;
		}
		if (!moved) break;
		sp = (sp + 1) % 4;
	}
	printf("%d %d", y, x);
	return 0;
}

 C. 개업 2

  한 번에 요리 가능한 방법은 두 가지가 있다.

1. 하나의 웍만 이용한다.

2. 두 개의 웍을 이용한다.

  그 다음 N에 대해서 차곡차곡 계산해나가는 방식을 이용한다. dp[k] = dp[k-한번에 요리 가능한 수] + 1로 점화식을 세우고 계산을 해준다. 시간 복잡도는 O(N^2)

>#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. 출근

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

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

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

#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. 세부

  첨에는 Maximum flow줄 알았다. 하지만 구하는 것은 단 한번 최대의 크기다.

  해보진 않았지만 이분탐색으로 풀 수 있는 문제긴 하다. BOJ 1939 중량제한 문제와 같다.

  하지만 나는 BFS + dp문제로 변형해서 해결했다.

  모든 방문점을 0으로 초기화시키고, BFS의 시작점은 INF로 두고, 각 방문점에 대해서 가능한 용량의 max값을 취해준다.

  dp[k] = k까지 갈 때, k로 가져갈 수 있는 금빼빼로의 최대 개수.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct _d { int v, w; };
vector<vector<_d>> adj;
int min_v(int a, int b) { return a < b ? a : b; }
int main() {
	int N, M, s, t, u, v, w,*dp;
	scanf("%d%d%d%d", &N, &M, &s, &t);
	dp = new int[N] {};
	s--, t--;
	adj.resize(N);	
	while (M--) {
		scanf("%d%d%d", &u, &v, &w);
		u--, v--;
		adj[u].push_back(_d{ v,w });
		adj[v].push_back(_d{ u,w });
	}
	queue<int> q;
	dp[s] = 1e9, q.push(s);
	while (!q.empty()) {
		u = q.front(), q.pop();
		for (_d& e : adj[u])
			if (dp[e.v] < min_v(dp[u], e.w)) {
				dp[e.v] = min_v(dp[u], e.w);
				q.push(e.v);
			}
	}
	printf("%d", dp[t]);
	return 0;
}

 G. 대문자

  솔루션을 참고했다.

  문자열의 길이를 L이라고 할 때, 끝부터 참고해서 dp를 구성한다. dp[k] = k번째 문자부터 L까지의 가능한 대문자 문자열 수

  

#include <cstdio>
#include <cstring>
const int MOD = 1000000007;
int main() {
	char S[1001];
	int dp[1001] = {}, L,i ,j,chk[26];
	scanf("%s", S);
	L = strlen(S);
	for (i = L; i >= 0; i--) {
		memset(chk, 0, sizeof(chk));
		dp[i] = 1;
		for (j = i; j < L; j++) {
			if (++chk[S[j] - 'a'] == 3) {
				dp[i] += dp[j + 1];
				dp[i] %= MOD;
			}
		}
	}
	printf("%d", (dp[0] + MOD - 1) % MOD);
	return 0;
}

  H. 세금