문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 높이에 몇개 벽이 있는지를 어떻게 기록할 것인가가 관건인 문제이다.
  • 이분탐색으로 풀 수도 있겠지만 내가 생각해낸 방법은 이거였다.
  • 일단 그냥 일일이 기록하면 시간 초과가 뜨게 된다.
  • prefix sum을 이용하면 효율적으로 풀 수 있다.
  • 만일 인풋이 5라고 하면 시작점부터 5까지 값이 모두 있다고 볼 수 있다.
  • 그렇기 때문에 각 기둥의 정보를 2개의 어래이로 받은 후 역으로 이전값을 현재값에 더해간 후 두 어레이를 더하면 기록은 끝난다.
  • 그런 후 2번의 서치를 통해 최소값과 최소값의 갯수를 찾아낸다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

int main(){
    int n, h, t1, t2, cnt = 0, ans = 500002;
    n = readInt(), h = readInt();
    vector<int> r1(h, 0), r2(h, 0);
    for(int i = 0; i < n / 2; i++){
        t1 = readInt(), t2 = readInt();
        r1[t1-1] ++, r2[t2-1] ++;
    }
    for(int i = h - 2; i >= 0; i--) r1[i] += r1[i+1], r2[i] += r2[i+1];
    for(int i = 0; i < h; i++){
        r1[i] += r2[h - i - 1];
        if(r1[i] < ans) ans = r1[i];
    }
    for(int i = 0; i < h; i++)if(r1[i] == ans) cnt++;
    printf("%d %d", ans, cnt);
}

느낀점

  • prefix sum을 떠올려낸 모든 이들에게 상을 드리고 싶다.
  • 나는 비록 생각해내지 못했다.. 오늘도 이렇게 나의 부족함을 배운다..ㅎㅎ