한국정보올림피아드 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;
}
3번 리조트 문제입니다.
경우의 수가 많지 않으니, 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;
}
'알고리즘 & Problem Solving > 한국정보올림피아드(KOI)' 카테고리의 다른 글
| KOI 2013 초등부 문제 풀이 (0) | 2018.02.06 |
|---|---|
| KOI 2014 초등부 문제 풀이 (0) | 2018.01.29 |
| KOI 2017 초등부 문제 풀이 (0) | 2018.01.28 |
| KOI 2015 초등부 문제 풀이 (0) | 2017.09.17 |
| KOI 1996 중등부 연속부분최대곱 (0) | 2017.06.27 |
