아인스트라세의 SW 블로그

한국정보올림피아드 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;
	}
}

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

문제들은 백준저지에서 참고하고 풀이했습니다.

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

총 4문제로 이루어지며, 뒤쪽 문제로 갈 수록 난이도가 어려워집니다.

1번 방 배정 문제입니다.

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

학년 별 인원수에 맞는 방을 배정한 뒤 모두 더해주면 됩니다.

방에 4명씩 있을 수 있다면, 실제 인원에 +3을 해준 뒤, 4로 나누어주면 각 학년 및 성별별로 필요한 방의 수가 나옵니다. C++에서 정수끼리 나눗셈을 할 시, 소수점 이하는 자동으로 버려지기 때문입니다.

예를들어 방에 5명이 있을 수 있고, 인원이 5명이라고 하면 5+4을 해서 9을 만든 뒤 5로 나누면 1.8이 되는데 소수점 버림으로 인하여 1이 됩니다. 5명일 시에는 방이 1개 필요한 것입니다.

비슷한 원리로 방에 5명이 있을 수 있고, 인원이 6명일 경우 6+4을 해서 10를 만든 뒤 5로 나누면 2가 됩니다.  6명이 묵기 위해서는 2개의 방이 필요한 것입니다.

#include <iostream>

#define GIRL 0
#define BOY 1
using namespace std;

int people[2][7];
int main() {
	int N, K;
	int ans = 0;
	int bias;
	cin >> N >> K;
	
	bias = K - 1;
	
	for (int i=0; i < N; i++) {
		int S, Y;
		cin >> S >> Y;
		people[S][Y]++;
	}
	for (int s = 0; s < 2; s++) {
		for (int y = 1; y < 7; y++) {
			if (people[s][y]) {
				ans += (people[s][y] + bias) / K;
			}
		}
	}
	cout << ans << endl;
	
}

2번 타일 장식물 문제입니다.

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

가로 세로 길이가 늘어나는 패턴이 짝수번째 홀수번째마다 규칙성을 갖고 연속됩니다. 이 규칙성만 찾으면 간단하게 해결할 수 있습니다.

#include <iostream>

using namespace std;
typedef long long ll;
int main() {
	ll x = 1, y = 1;
	int N;
	cin >> N;
	for (int i = 1; i < N; i++) {
		if (i & 1) {
			y += x;
		} else {
			x += y;
		}
	}
	
	cout << ((x+y)<<1) << endl;
}

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>

#define MIN(a,b) ((a) < (b) ? (a) : (b))
using namespace std;

vector<int> holiday;
vector<bool> day;
int total_day, absent_day;
int cost[101][101];

int count = 0;
int count_mem = 0;
int find_cost(int start_day, int num_coupon) {
	count ++;
	int min_cost = 987654321;
	int temp, a,b;
	temp = 987654321;
	if (start_day > total_day) {
		//basis case
		return 0;
	} else if (!day[start_day]) {
		
		for (int i=start_day+1; i<=total_day; i++) {
			if (day[i]) {
				return find_cost(i, num_coupon);
			}
		}
		return 0;
	}
	
	if (cost[start_day][num_coupon] == 0) {
		if ( start_day <= total_day - 2 && day[start_day+1] && day[start_day+2] ) {
			
		} else {
			min_cost = MIN(min_cost, find_cost(start_day + 1, num_coupon) + 10000 );
		}
		
		if (min_cost != temp) {
			temp = min_cost;
			a = start_day + 1;
			b = num_coupon;
		}
		
		if ( start_day <= total_day - 5 && day[start_day+1] && day[start_day+2] && day[start_day+3] && day[start_day+4]) {
		} else {
			min_cost = MIN(min_cost, find_cost(start_day + 3, num_coupon + 1) + 25000 );
		}
		
		if (min_cost != temp) {
			temp = min_cost;
			a = start_day + 3;
			b = num_coupon + 1;
		}
		
		min_cost = MIN(min_cost, find_cost(start_day + 5, num_coupon + 2) + 37000 );
		
		if (min_cost != temp) {
			temp = min_cost;
			a = start_day + 5;
			b = num_coupon + 2;
		}
		
		if (num_coupon >= 3) {
			min_cost = MIN(min_cost, find_cost(start_day + 1, num_coupon - 3) );
			
			if (min_cost != temp) {
				a = start_day + 1;
				b = num_coupon - 3;
			}

		}
		cost[start_day][num_coupon] = min_cost;
		return min_cost;
	} else {
		count_mem++;
		return cost[start_day][num_coupon];
	}
	
	
}
int main() {
	int temp;
	int answer;
	
	scanf("%d %d\n", &total_day, &absent_day);
	holiday.reserve(absent_day);
	day.resize(total_day + 1, true);

	for (int i=0;i<absent_day; i++) {
		scanf("%d ", &temp);
		holiday.push_back(temp);
	}
	
	for (int i=0;i<absent_day; i++) {
		day[holiday[i]] = false;
	}
	
	answer = find_cost(1, 0);
	cout << answer;
}

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

typedef struct {
	int x, yl, yh;
} barPos;

typedef pair<int, int> meta;
bool operator<(barPos a, barPos b) {
	return a.x < b.x;
}

vector<barPos> barriers;
vector<int> answer;
set<meta> subp;
void dump_barrier() {
	cout << " --------------------------------------" << endl;
	for (int i=0; i < barriers.size(); i++) {
		cout << barriers[i].x << " " << barriers[i].yl << " " << barriers[i].yh << endl;
	}
	cout << " --------------------------------------" << endl;
}
void dump_subp() {
	for (set<meta>::iterator ptr = subp.begin(); ptr != subp.end(); ptr++) {
		cout << ptr->first << ", " << ptr->second << endl;
	}
}
int find_min_y() {
	int min_val = 98754321;
	for (set<meta>::iterator ptr = subp.begin(); ptr != subp.end(); ptr++) {
		min_val = min(min_val, ptr->second);
	}
	return min_val;
}
void set_answers(int min_val) {
	for (set<meta>::iterator ptr = subp.begin(); ptr != subp.end(); ptr++) {
		if (ptr->second == min_val) {
			answer.push_back(ptr->first);
		}
	}
}
int main() {
	int N;
	int srcY, finX;
	
	cin >> N >> srcY >> finX;
	barriers.reserve(N);
	
	for (int i=0; i < N; i++) {
		int x, yl, yh;
		
		cin >> x >> yl >> yh;
		barPos tmp;
		tmp.x = x;
		tmp.yl = yl;
		tmp.yh = yh;
		barriers.push_back(tmp);
	}
	sort(barriers.begin(), barriers.end());
	subp.insert(make_pair(srcY, 0));
	vector<set<meta>::iterator> delete_candidate;
	for (int i=0; i < N; i++) {
		auto upper_bound = barriers[i].yh;
		auto lower_bound = barriers[i].yl;
		delete_candidate.clear();
		int minl = 987654321;
		int minh = 987654321;
		for (set<meta>::iterator ptr = subp.lower_bound(make_pair(lower_bound, 0)); ptr != subp.upper_bound(make_pair(upper_bound, 0)); ptr++) {
			delete_candidate.push_back(ptr);
			minl = min(minl, ptr->second + (ptr->first - lower_bound));
			minh = min(minh, ptr->second + (upper_bound - ptr->first));
		}
		for (int j=0; j < delete_candidate.size(); j++) {
			subp.erase(delete_candidate[j]);
		}
		if (delete_candidate.size() > 0) {
			delete_candidate.clear();
			subp.insert(make_pair(upper_bound, minh));
			subp.insert(make_pair(lower_bound, minl));
		}
	}
	
	int min_y_val = find_min_y();
	set_answers(min_y_val);
	
	cout << finX + min_y_val << endl << answer.size();
	for (int i=0; i < answer.size(); i++) {
		cout << ' ' << answer[i];
	}
	cout << endl;
}

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

첫번째 포스팅입니다.

한국정보올림피아드 1996년도 중등부 1번문제 연속부분최대곱 문제를 풀어봤습니다.

흔하디 흔한 dp(dynamic programming)으로 풀었습니다.

dp[i]는 i번째 수열에서 끝나는 부분수열의 최대곱을 저장합니다.

가령 arr이 원래 수열이라고 하면

dp[0]은 arr[0]

dp[1]는 arr[0] * arr[1]

dp[2]은 arr[0] * arr[1] * arr[2]

dp[3]은 arr[0] * arr[1] * arr[2] * arr[3]

dp[4]은 arr[0] * arr[1] * arr[2] * arr[3] * arr[4]

dp[5]은 arr[0] * arr[1] * arr[2] * arr[3] * arr[4] * arr[5]

dp[6]은 arr[0] * arr[1] * arr[2] * arr[3] * arr[4] * arr[5]

dp[7]은 arr[7]

이 됩니다.

dp[7]의 경우를 제외하고 항상 더 곱하는것이 좋은 결과를 가져오는데, dp[6]의 경우 1보다 작으므로, dp[7]에서는 이전 앞의 누적 곱을 제외하고 본인만 가져가는것이 이득이므로 dp[7] = arr[7]이 됩니다.

출력 시, 포맷 스트링으로 %.3lf를 사용하면 소수점 4번째 자리에서 자동 반올림된 값이 나타나는 것을 처음 알았네요.

반올림 된 값으로 출력만 할 경우 유용할 것 같습니다.

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

typedef double vt;

int N;
vector<vt> arr;
vector<vt> dp;

int main() {
	cin >> N;
	
	arr.reserve(N);
	dp.reserve(N+1);
	for (int i=0; i < N; i++) {
		vt val;
		cin >> val;
		arr.push_back(val);
	}
	dp[0] = arr[0];
	for (int i=1; i <= N; i++) {
		if (dp[i-1] > 1) {
			dp[i] = dp[i-1] * arr[i];
		} else {
			dp[i] = arr[i];
		}
	}
	vt max_val = -987654321;
	for (int i=0; i < N; i++) {
		max_val = max(max_val, dp[i]);
	}
	printf("%.3lf\n", max_val);
	
}