BOJ2457: 공주님의 정원

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

  • 스위핑 문제가 까다롭다는게 팍 느껴짐
  • 일단 고려해야할 조건이 많고, 실수할 여지가 많음
  • 이번에는 꽉 채우는 유형의 문제인데, 한 오른쪽 바운드로 역순으로 정렬한 뒤에 봄
  • 4가지 케이스로 나눠서 보면 됨
    1. 목표한 rBound를 안, 왼쪽 끝까지 도달 못하는 경우 -> lMin을 계산
    2. 목표한 rBound를 안, 왼쪽 끝까지 도달하는 경우 -> cnt를 리턴
    3. 목표한 rBound를 밖, 새로운 r이 지금까지 쌓은 lMin보다 작은경우 -> 0을 리턴
    4. 목표한 rBound를 밖, 새로운 r이 지금까지 쌓은 lMin 보다 큰경우 -> rBound를 수정, 카운트 증가
  • 마지막에는 미쳐 판단못해준 lMin이 도달했는지 봐줘야함
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

struct Segment {
  int l, r;
  bool operator<(const Segment& b) const {
    return r > b.r;
  }
};

class SegmentLength {
  int N;
  vector<Segment> segments;

public:
  void input();
  int sweep();
};

void SegmentLength::input() {
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    int m1, d1, m2, d2;
    scanf("%d %d %d %d", &m1, &d1, &m2, &d2);
    segments.push_back({m1*100+d1, m2*100+d2});
  }
}

int SegmentLength::sweep() {
  sort(segments.begin(), segments.end());
  int rBound = 1131, lMin = 9999, cnt = 1;
  for (auto [l, r] : segments) {
    if(r >= rBound) {
      lMin = min(lMin, l);
      if (lMin <= 301)
        return cnt;
    } else if(r < lMin) {
      return 0;
    } else {
      rBound = lMin;
      lMin = l;
      cnt++;
    }
  }
  return lMin <= 301 ? cnt : 0;
}

int main() {
  SegmentLength sl;
  sl.input();
  cout << sl.sweep();
}