한국정보올림피아드(정올) 2017년도 초등부 문제 풀이 포스팅입니다.
문제들은 백준저지에서 참고하고 풀이했습니다.
https://www.acmicpc.net/category/detail/1775
총 4문제로 이루어져 있는데, 제가 풀 때 당시에는 백준저지에는 3문제만 올라와있어서 3문제에 대한 코드만 올립니다.
https://www.acmicpc.net/problem/14697
2번, 방 배정하기 문제입니다. (백준저지 14697)
N값이 작으므로 3중 포문으로 O(N^3)으로 완전탐색으로 Naive하게 풀었습니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, total;
cin >> a >> b >> c >> total;
int a_lim = total/a;
int b_lim = total/b;
int c_lim = total/c;
for (int i=0; i <= c_lim; i++) {
int cur = c * i;
for (int j=0; j <= b_lim; j++) {
int cur2 = cur + j*b;
for (int k=0; k <= a_lim; k++) {
int cur3 = cur2 + k*a;
if (cur3 == total) {
cout << 1 << '\n';
return 0;
}
}
}
}
cout << 0 << '\n';
return 0;
}
https://www.acmicpc.net/problem/14863
3번, 서울에서 경산까지 문제입니다. (백준저지 14863)
DFS를 통한 완전탐색으로 풀되, 중복되어 풀리는 문제들(Overlapping-subproblems)는 Memoization 패턴을 이용하여 중복해서 풀리지 않도록 처리했습니다. 그리고 마지막 구간까지 도달하지 못하는 경우에 대해서 제외하도록 처리해야하는 것이 좀 까다로웠습니다.
#include <bits/stdc++.h>
using namespace std;
#define IMPOSSIBLE -987654321
typedef long long ll;
int dp[101][100001]; //[range][minute left]
int walk_min[101];
int walk_get[101];
int bicy_min[101];
int bicy_get[101];
int n, k;
int get(int segment, int minute_left) {
if (segment >= n) return 0;
if (minute_left <= 0) return IMPOSSIBLE;
int& ret = dp[segment][minute_left];
if (ret != -1) {
return ret;
};
ret = IMPOSSIBLE;
if (minute_left >= walk_min[segment] and get(segment+1, minute_left - walk_min[segment]) != IMPOSSIBLE) {
ret = max(ret, get(segment+1, minute_left - walk_min[segment]) + walk_get[segment]);
}
if (minute_left >= bicy_min[segment] and get(segment+1, minute_left - bicy_min[segment]) != IMPOSSIBLE) {
ret = max(ret, get(segment+1, minute_left - bicy_min[segment]) + bicy_get[segment]);
}
return ret;
}
int main() {
scanf("%d %d", &n, &k);
for (int i=0; i < n; i++) {
scanf("%d %d %d %d", &walk_min[i], &walk_get[i], &bicy_min[i], &bicy_get[i]);
}
memset(dp, -1, sizeof(dp));
cout << get(0, k) << '\n';
return 0;
}
https://www.acmicpc.net/problem/14864
4번, 줄서기 문제입니다. (백준저지 14864)
개인적으로 난이도가 꽤나 있었고, 완전 Nice한 해답은 아니라고 생각합니다.
일단 순서쌍에서 알아낼 수 있는 정보는 다음과 같습니다.
1. 나보다 뒤에 있는 놈에 대해서, 내가 그 놈보다 큰지 아닌지를 확인할 수 있다.
2. 나보다 앞에 있는 놈 중에 나보다 큰 놈이 몇 개인지 알 수 있다.
물론 나보다 앞에 있는 놈 중에 큰놈이 몇개인지 뿐만 아니라 누군지까지 확인할 수 있지만, 일단은 저 두개를 이용해서 문제를 풀어보았습니다.
맨 뒤에서 부터 채워가면서 숫자를 넣을 것인데, 일단 집합 S를 다음과 같이 초기화 합니다. S = {1, 2, 3, ... , N}
맨 뒤에있는 숫자 입장에서는 나머지 모두가 나보다 앞에 있으므로, 나머지 수 중 자신보다 큰 수가 몇개인지 알 수 있습니다.
그러면 앞에있는 수 중 자신보다 큰 수의 개수를 k라고 하면, 집합 S에서 k번째 큰 수를 빼서 자신의 값에 집어넣습니다.
이런식으로 맨 앞까지 진행합니다.
이러면 일단 조건을 만족할만한 정답 셋을 하나 구할 수 있는데, Valid한 정답을 갖는다면 Unique한 정답을 가질 것입니다.
하지만 해당 인풋이 Invalid할 수도 있으니 한번 체크를 해야 합니다. (Invalid한 정답이라면 -1를 출력해야함)
이때 Strict하게 체크를 하려면 자신보다 뒤에 있는 숫자 중, 순서쌍에 해당된다면 자신보다 작은지, 순서쌍에 해당되지 않는다면 자신보다 큰지를 확인해야하는데, 둘다 체크하게 되면 TLE가 날 것입니다.
특히나 순서쌍애 해당되지 않는 애들까지 체크를 하게 되면 O(N^2)이므로 꼼짝없이 TLE다. 하지만 순서쌍 개수는 100만개이므로, 순서쌍에 해당되는 경우만 체크할 경우 TLE는 안날 수 있습니다. 따라서 순서쌍에 해당되는 경우만 자신보다 작은 값을 갖는지만 체크하면 됩니다.
이 부분의 경우 -1이 정답인데 아니게 나올까봐 조마조마했는데 정답 판정이 났다. 아마 앞에서 만든 Answer Array가 주어진 순서쌍 조건이 맞는지만 확인해도빠진 조건이 있는 반례가 없다는게 논리적으로 맞아서 그런 것인지는 잘 모르겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define NUM_STUDENT 100001 //학생수 최대
#define UNDEFINED 0 // 정답이 결정되지 않은 상태
set<int> larger_than_me[NUM_STUDENT], smaller_than_me[NUM_STUDENT];
int ans[NUM_STUDENT];
int n, m;
set<int> rest;
void fail() {
cout << -1 << '\n';
exit(EXIT_SUCCESS);
}
int main() {
scanf("%d%d", &n, &m);
//initialize rest set
for (int i=1; i<=n;i++) {
rest.insert(-i);
}
//initialize rest set
if (n == 1) { //학생수 1명일때만 예외처리
cout << 1 << '\n';
return 0;
}
for (int i=0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b); // a > b라는 뜻
smaller_than_me[a].insert(b); // a보다 작은 set에 b 추가.
larger_than_me[b].insert(a);// b보다 큰 set에 a추가.
}
for (int cur = n; cur >= 1; cur--) {
int larger_num = larger_than_me[cur].size();
auto it = rest.begin();
for (int i=0; i < larger_num; i++) {
it++;
}
int kth_largest = -*it;
ans[cur] = kth_largest;
rest.erase(it);
}
//check for validation - 주어진 조건은 맞는지 확인. 빠진 조건이 있는지는 안확인 ㅎㅎㅎ
for (int cur = 1; cur < n; cur++) {
int my_val = ans[cur];
for (auto it : smaller_than_me[cur]) {
int smaller_val = ans[it];
if (smaller_val > my_val) {
fail();
}
}
}
for (int i=1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}