KOI 2015 초등부 문제 풀이

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

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

1번 사과문제입니다.

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

apple수를 사람수로 나누면 1인당 지급되는 사과수가 됩니다.

#include <iostream>

using namespace std;

int main() {
	int N;
	cin >> N;
	
	int ans = 0;
	while(N--) {
		int std, apple;
		cin >> std >> apple;
		int cnt = apple/std;
		int total = cnt * std;
		ans += apple - total;
	}
	cout << ans << endl;
}

2번 벨트문제입니다.

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

정수로 떨어지게 되어있으므로 그냥 계산하면 됩니다.

#include <iostream>

using namespace std;

int main() {
	int M;
	bool direction = false;
	int rot = 1;
	cin >> M;
	
	while (M--) {
		int a, b;
		int dir;
		cin >> a >> b >> dir;
		rot *= b;
		rot /= a;
		if (dir == 1) {
			direction = !direction;
		}
	}
	cout << (direction == true ? "1" : "0") << " " << rot << endl;
}

3번 카드문제입니다.

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

완전탐색을 하면 시간 초과가 난다. O(3^n)이 된다. 하지만 중복탐색되는 부분을 줄이면, 즉 Memoziation원리를 적용한 Dynamic programming으로 풀 시에는 나타나는 좀더 효율적으로 풀 수 있다. dp[왼쪽남은카드수][오른쪽남은카드수]로 한다면 최악의경우 O(n^2)이므로 2000^2 = 400만으로 1초안에 풀 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> L, R;
int n;

int dp[2001][2001];
bool chk[2001][2001];

int get(int l, int r) {
	if (l <= 0 || r <= 0) {
		return 0;
	}
	if (chk[l][r]) return dp[l][r];

	int ret;
	
	ret = max(get(l-1, r-1), get(l-1, r));
	int left_top_card_val = L[n-l];
	int right_top_card_val = R[n-r];
	if (left_top_card_val > right_top_card_val) {
		ret = max(ret, get(l, r-1) + right_top_card_val);
	}
	chk[l][r] = true;
	return dp[l][r] = ret;
}
int main() {
	cin >> n;
	L.reserve(n);
	R.reserve(n);

	for (int i=0; i < n; i++) {
		int tmp;
		cin >> tmp;
		L.push_back(tmp);
	}
	for (int i=0; i < n; i++) {
		int tmp;
		cin >> tmp;
		R.push_back(tmp);
	}
	cout << get(n, n) << endl;
}

4번 여왕별 문제입니다.

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

dfs로는 Time out이 납니다.. 그러므로 더 좋은 성능의 방법을 찾아봐야 합니다.

숫자가 감소하지 않는 방향이라고 했으니 규칙을 잘 보면, 왼쪽 끝과 위쪽 끝을 제외하고 내부쪽은 결과적으로 위쪽 값과 같은 값을 갖게 됩니다.

이러한 규칙을 이용하면 O(MN)으로 해결 가능합니다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> border;

int main() {
	int M, N;
	cin >> M >> N;
	int len = M*2 - 1;
	border.resize(len, 1);
	while(N--) {
		int zero, one, two;
		cin >> zero >> one >> two;
		for (int i=zero; i < zero + one; i++) {
			border[i]++;
		}
		for (int i = zero+one; i < len; i++) {
			border[i] += 2;
		}
	}
	
	for (int i=0; i < M; i++) {
		for (int j=0; j < M; j++) {
			if (j==0) {
				cout << border[M-i-1] << ' ';
			} else {
				cout << border[M+j-1] << ' ';
			}
		}
		cout << endl;
	}
}