KOI 2013 초등부 문제 풀이

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

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

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

총 4문제가 있습니다.

1번 올림픽 문제입니다. (백준 8979번)

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

단순 계산으로 풀 수 있다. 비교 연산자를 재정의해서 정렬한 뒤, 중복 순위의 경우에만 체크를 해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
struct data {
    int num, gold, silver, bronze;
    
    bool operator < (const data& rhs) const {
        return gold != rhs.gold ? gold > rhs.gold : (silver != rhs.silver ? silver > rhs.silver : bronze > rhs.bronze);
    }
    bool operator == (const data& rhs) const {
        return gold == rhs.gold && silver == rhs.silver && bronze == rhs.bronze;
    }
};
vector<data> arr;
int main() {
    int n, k;
    cin >> n >> k;
    arr.reserve(n);
    for (int i=0; i < n; i++) {
        data tmp;
        scanf("%d %d %d %d\n", &tmp.num, &tmp.gold, &tmp.silver, &tmp.bronze);
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end());
    
    int rank = 0;
    int accu = 1;
    data prev;
    prev.gold = prev.silver = prev.bronze = -1;
    //dump
    for (int i=0; i < n; i++) {
        auto& a = arr[i];
        if ( (prev == a) == false) {
            rank += accu;
            accu = 1;
        } else {
            accu++;
        }
        // printf("rank %d - ", rank);
        if (a.num == k) {
            cout << rank << '\n';
            return 0;
        }
        
        prev = a;
        // printf("(%d) %d, %d, %d\n", a.num, a.gold, a.silver, a.bronze);
    }
    //dump
}

2번 택배 문제입니다.

https://www.acmicpc.net/problem/8980 (백준 8980번)

그리디로 풀 수 있다. 그리디도 그리딘데, 어떤식으로 그리디를 적용시킬지가 중요하다. 일단 배달 구간이 가장 짧은놈들 순서대로 sorting한다. 배달 구간이 짧을수록 트럭에서 공간을 점유하는 시간이 작아지므로 그렇게 하는 것이다.    

그리고 배달구간이 짧은놈 순서대로 트럭에 최대한 집어넣으면 정답이 된다. 이것을 어떻게 구현하느냐에서 많이 해맸는데, 궂이 시간순대로 트럭이 이동하는 방식으로 시뮬레이션을 하지 않더라도 짧은 구간부터, 구간별 트럭에 적제된 화물양을 저장해놓았다가 최대한 적재시키는 식으로 정답을 구하면 쉽게 풀이가 된다.

 

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii; //src, dst
struct Order {
    int src, dst, size;
};

Order orders[10001];

bool cmp(const struct Order& lhs, const struct Order& rhs) {
    if (lhs.dst != rhs.dst) return lhs.dst < rhs.dst;
    return lhs.src < rhs.src;
}
int loaded[2001]; //해당 위치에 있을 때, 트럭에 차있는 양
int main() {
    int ans = 0;
    int n, c, m;
    cin >> n >> c >> m;
    for (int i=0; i < m; i++) {
        scanf("%d %d %d", &orders[i].src, &orders[i].dst, &orders[i].size);
        
    }
    
    sort(orders, orders + m, cmp);
    for (int i=0; i< m; i++) {
        auto& order = orders[i];
        int already_loaded_amount = 0;
        for (int pos = order.src; pos < order.dst; pos++) { //구간을 돌면서 가장 많이 적제된 양을 찾는다.
            if (loaded[pos] > already_loaded_amount) {
                already_loaded_amount = loaded[pos];   
            }
        }
        int can_be_more_load_amt = min(order.size, c - already_loaded_amount); //더 적재할 양을 고른다.
        for (int pos = order.src; pos < order.dst; pos++) { //구간에 적재 시킨다.
            loaded[pos] += can_be_more_load_amt;
        }
        ans += can_be_more_load_amt;
    }    
    cout << ans <<'\n';
    return 0;
}

3번 입력숫자 문제입니다.

https://www.acmicpc.net/problem/8981 (백준 8981번)

비슷한 로직으로 하면 역연산이 된다. 이전 값 만큼 offset을 앞으로 전진시키고, 해당 위치에 다음 받은 값을 쓴다. 만약 거기 이미 값이 있다면 값이 없을 때 까지 앞으로 전진하면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int arr[30];
int input[30];
int ptr;
int val;
int n;
void search() {
    while(arr[ptr]) {
        ptr++;
        ptr %= n;
    }
}
int main() {
    cin >> n;
    cin >> val;
    arr[ptr] = val;
    for (int i=1; i < n; i++) {
        ptr += val;
        ptr %= n;
        search();
        cin >> input[i];
        arr[ptr] = val = input[i];
    }
    
    cout << n << endl;
    for (int i=0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << '\n';
	return 0;
}