KOI 2017 초등부 문제 풀이

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