[정렬] 백준 3020 :: 개똥벌레

개똥벌레 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	3922	1428	1058	38.854%

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

예제 입력 1 

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

예제 출력 1 

7 2

  

     

 문제 풀이

1차 풀이 (  4600 KB,  76 ms)

• 데이터가 많으므로 stdio와 동기화 해제.
• 먼저, 종유석과 석순을 각각 정렬.
• 각 높이의 경우마다, 통과하는 종유석과 석순의 수를 계산.
  정렬되어 있으므로, 이분 탐색을 사용해 첫 번째로 만나는 방해물의 크기를 획득.
• 첫 번째로 만나는 방해물보다 큰 방해물은 당연히 부딪치므로,
  부딪친 총 개수를 log(n) 시간에 계산할 수 있음.
• 부딪친 개수를 결과배열에 넣고 정렬하고,
  가장 작은 요소와, 그 개수를 출력.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int N, H, half;
        cin >> N >> H;
        half = N/2;

        int up[half], dn[half], ret[H+1];
        memset(ret, 0, sizeof ret);
        for(int i=0; i<half; i++){
                cin >> dn[i] >> up[i];
        }
        sort(dn, dn+half);
        sort(up, up+half);

        for(int i=1; i<=H; i++){
                unsigned long cross = 0;
                cross += dn + half - lower_bound(dn, dn+half, i);
                cross += up + half - upper_bound(up, up+half, H-i);
                ret[i] = (int) cross;
        }
        sort(ret+1, ret+H+1);
        cout << ret[1] << ' ' << upper_bound(ret+1, ret+H+1, ret[1]) - (ret+1);

}

2차 풀이 (  3820 KB,  24 ms)

• 데이터가 많으므로 stdio와 동기화 해제.
• dx[i] = i-1번째 칸에서 올라왔을 때, 부딪치는 방해물의 증감.
• 높이 1에서 시작하여 dx[i] 만큼 계속 더하면서 최솟값과 개수를 갱신.
  

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        int N, H, half;
        cin >> N >> H;
        half = N/2;

        int up, down, dx[H];
        memset(dx, 0, sizeof dx);
        for(int i=0; i<half; i++){
                cin >> up >> down;
                --dx[down];
                ++dx[H-up];
        }

        int cur_val = N/2;
        int ret_val = N+1, ret_cnt = 1;
        for(int i=0; i<H; i++){
                cur_val += dx[i];
                if(cur_val < ret_val) {
                        ret_val = cur_val;
                        ret_cnt = 1;
                }
                else if(cur_val == ret_val) {
                        ret_cnt++;
                }
        }
        cout << ret_val << ' ' << ret_cnt;
}

3차 풀이 (  5868 KB,  8 ms)

• 저수준 입출력 사용.
  

#include <iostream>
#include <cstring>
using namespace std;

const int BUF_SIZE = 1 << 20;        // 메모리 초과 가능, 적당히 조절할 것.
char input_buf[BUF_SIZE], output_buf[BUF_SIZE];
int input_buf_pos, output_buf_pos;
enum io_mode {READ, WRITE};
inline void char_io(io_mode mode, char &target)
{
        if(mode == READ) {
                if (input_buf_pos == BUF_SIZE)
                {
                        fread(input_buf, sizeof(char), BUF_SIZE, stdin);
                        input_buf_pos = 0;
                }
                target = input_buf[input_buf_pos++];
        }
        else {
                if(output_buf_pos == BUF_SIZE || target == EOF)
                {
                        fwrite(output_buf, sizeof(char), output_buf_pos, stdout);
                        output_buf_pos = 0;
                }
                output_buf[output_buf_pos++] = target;
        }
}
inline void char_io(io_mode mode, char &&target){
        char_io(mode, target);
}
inline void int_io(io_mode mode, int &target)
{
        char c;
        if(mode == READ){
                bool negative = false;
                int ret = 0;
                while(true)
                {
                        char_io(READ, c);
                        if(c == '\n' || c == ' ') break;
                        if(c == '-') {
                                negative = true;
                                continue;
                        }
                        ret = ret * 10 + (c & 0b1111);
                }
                target = negative ? -ret : ret;
        }
        else {
                int abs = target;
                int div = 1'000'000'000;
                char quotient = 0;
                if(abs < 0) {
                        char_io(WRITE, '-');
                        abs *= -1;
                }
                while(abs < div && div != 1) { div /= 10; }
                while(div != 0){
                        quotient = '0' + (char)((abs / div)%10);
                        char_io(WRITE, quotient);
                        div /= 10;
                }
        }
}
inline void int_io(io_mode mode, int &&target){
        int_io(mode, target);
}

int main() {
        int N, H, half;
        int_io(READ, N);
        int_io(READ, H);
        half = N/2;

        int up, down, dx[H];
        memset(dx, 0, sizeof dx);
        for(int i=0; i<half; i++){
                int_io(READ, up);
                int_io(READ, down);
                --dx[down];
                ++dx[H-up];
        }

        int cur_val = N/2;
        int ret_val = N+1, ret_cnt = 1;
        for(int i=0; i<H; i++){
                cur_val += dx[i];
                if(cur_val < ret_val) {
                        ret_val = cur_val;
                        ret_cnt = 1;
                }
                else if(cur_val == ret_val) {
                        ret_cnt++;
                }
        }
        int_io(WRITE, ret_val);
        char_io(WRITE, ' ');
        int_io(WRITE, ret_cnt);
        char_io(WRITE, EOF);
}