KOI 2016 초등부 문제 풀이

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

a

3번 리조트 문제입니다.

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

 경우의 수가 많지 않으니, DFS로 완전탐색을 하면 쉽게 찾을 수 있습니다. 쿠폰을 항상 쓰는 것이 능사가 아닌 케이스가 있다는 것을 조심해야합니다. 그런데 그냥 DFS를 하면 중복 케이스를 찾는 오버해드때문에 타임아웃이 날 수 있으므로, Memoization을 활용한 동적 프로그래밍의 테크닉도 섞어주어야 합니다.

#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;
}

4번 장애물 경기 문제입니다.

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

솔루션 해결에 많은 고민을 했습니다. 이게 초등부 문제가 맞는지 의심이 갈 정도였습니다. ㅠㅠ

이 문제는 해답을 보고 풀기도 했고, 100% 이해를 하고 난 문제가 아니라서 지금은 정확한 풀이가 잘 기억은 나지 않습니다만, 아래 코드는 정답 인정이 되는 코드입니다.

#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;
}