KOI 2010 초등부 문제 풀이

https://www.acmicpc.net/category/detail/340

KOI 2010 초등부

 

한국정보올림피아드 초등부 2010년도 문제 풀이입니다.

 

총 3문제가 있습니다.

 

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

2467번: 용액

 

1번 용액 (백준 2467)

1번 용액 문제입니다.

 

1번 문제치곤 조금 난이도가 있는 문제라고 생각합니다.

 

처음에는 바이너리 서치를 이용해서 O(NlgN)으로 풀이를 해 보았습니다.

A번째 용액, B번째 용액을 골라서 확인을 하되, A번째 용액에 대해서는 for문 을 돌고, 각각 A번째용액에 대하여, B번째 용액을 결정할 때, 바이너리 서치 개념을 적용해서 풀어보았습니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int a[100005];
int n;
int f, s, val;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
	}
	f = a[0];
	s = a[1];
	val = abs(f+s);
	for (int i = 0; i < n - 1; i++) {
		int first = a[i];

		int left = i + 1; // [left, right]
		int right = n - 1;
		while (left < right) {
			int mid = (left + right) / 2;
			int& second = a[mid];
			int sum = first + second;
			if (sum < 0) {
				if (abs(sum) < val) {
					val = abs(sum);
					f = first;
					s = second;
				}
				left = mid + 1;
			}
			else if (sum > 0) {
				if (abs(sum) < val) {
					val = abs(sum);
					f = first;
					s = second;
				}
				right = mid;
			}
			else {
				cout << first << ' ' << a[mid] << endl;
				return 0;
			}
		}
		int second = a[right];
		int sum = first + second;
		if (abs(sum) < val) {
			val = abs(sum);
			f = first;
			s = second;
		}
		second = a[left];
		sum = first + second;
		if (abs(sum) < val) {
			val = abs(sum);
			f = first;
			s = second;
		}
	}
	cout << f << ' ' << s << endl;
	return 0;
}

 

이 풀이 외에도 O(N)으로도 풀이가 가능하다는 것을 알게 되었습니다.

 

배열이 정렬되어 있기 때문에, A번째에서 A+1번째로 이동할 때, 더 0에 가까운 값을 구하기 위해서는 B에서 B-1로 이동하는 경우는 있을 수 있으나 B+1에서 더 0에 가까운 값이 나올 수는 없기에 그리디하게 투포인터 형식으로 풀 수있습니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int arr[100005];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", arr + i);
	}
	int a, b, val;
	a = arr[0], b = arr[n - 1];
	val = abs(a + b);
	int left = 0;
	int right = n - 1;
	while (left < right) {
		int l, r, sum;
		l = arr[left];
		r = arr[right];
		sum = l + r;
		if (abs(sum) < val) {
			val = abs(sum);
			a = l;
			b = r;
		}
		if (sum > 0) {
			right--;
		}
		else {
			left++;
		}
	}
	printf("%d %d\n", a, b);
}

코드도 훨씬 간단합니다.

 

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

2468번: 안전 영역

 

2번 안전영역 (백준 2468)

2번 문제 안전영역입니다.

 

N값이 100으로 별로 크지 않으므로, BFS혹은 DFS로 Flood-Fill해서 안전지역 개수를 세면 되고, 높이 값이 1~100이므로, 100번 해 주면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int field[101][101];
bool visit[101][101];
int n;
bool isin(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < n;
}
const int dx[] = { +1, -1, +0, +0 };
const int dy[] = { +0, +0, +1, -1 };
void dfs(int x, int y, int h) {
	//visit[x][y] = true;
	for (int k = 0; k < 4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (isin(nx, ny) && field[nx][ny] > h) {
			if (visit[nx][ny] == false) {
				visit[nx][ny] = true;
				dfs(nx, ny, h);
			}
		}
	}
}
int check(int h) {
	int ret = 0;
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visit[i][j] == false && field[i][j] > h) {
				visit[i][j] = true;
				ret++;
				dfs(i, j, h);
			}
		}
	}
	return ret;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> field[i][j];
		}
	}
	int ans = 1;
	for (int i = 1; i <= 101; i++) {
		ans = max(ans, check(i));
	}
	cout << ans << endl;
	return 0;
}

 

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

2469번: 사다리 타기

3번 사다리 타기 (백준 2469)

3번 사다리 타기 문제입니다.

 

사다리를 타서 모양을 맞출 수 있느냐와 관련된 문제입니다.

 

양방향 dfs의 개념을 적용하면 간단하게 풀어 볼 수 있습니다.

Meet in the middle 이라는 개념과도 좀 비슷할 수 있습니다.

 

시작 시 알파뱃 배치와 종료시 알파뱃 배치 둘다 알기 때문에, 위에서 내려오고 아래에서 올라와서 모르는 사다리 배치 전후의 배열을 알아냅니다.

 

그리고 그 전 후 배열을 사다리 한 줄로 적용해서 변환 가능한지에 따라 풀어내면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
void fail(int k) {
	while (--k) {
		cout << 'x';
	}
	cout << endl;
	exit(EXIT_SUCCESS);
}
int main() {
	string lines[1005];
	int k, n;
	int q;
	cin >> k >> n;
	string first;
	string fin;
	string ans = "";
	cin >> fin;
	for (int i = 0; i < k; i++) {
		first += ('A' + i);
	}
	for (int i = 0; i < n; i++) {
		cin >> lines[i];
		if (lines[i][0] == '?') q = i;
	}
	for (int i = 0; i < q; i++) {
		for (int j = 0; j < lines[i].length(); j++) {
			char& ch = lines[i][j];
			if (ch == '-') {
				swap(first[j], first[j + 1]);
			}
		}
	}
	for (int i = n - 1; i > q; i--) {
		for (int j = 0; j < lines[i].length(); j++) {
			char& ch = lines[i][j];
			if (ch == '-') {
				swap(fin[j], fin[j + 1]);
			}
		}
	}

	for (int i = 0; i < k - 1; i++) {
		char up = first[i];
		char down = fin[i];
		if (up != down) {
			ans += "-";
			if (i + 2 < k) {
				ans += "*";
				i++;
			}
		}
		else {
			ans += "*";
		}
	}
	for (int i = 0; i < ans.length(); i++) {
		if (ans[i] == '-') {
			swap(first[i], first[i + 1]);
		}
	}
	if (first != fin) fail(k);
	cout << ans << endl;
}