Why Did the Cow Cross the Road (Silver)

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

14464번: 소가 길을 건너간 이유 4

1. 처음 시도했던 틀린 풀이 

- '대체제(도와줄 수 있는 닭의 수)가 적은 소들을 우선적으로 처리해주자' (greedy)

- 소마다 길을 건너게 도와줄 수 있는 닭들을 모두 찾아서 리스트를 만들어 놓는다.

- 도와줄 수 있는 닭이 가장 적은 순으로 정렬을 시도한다.

- 아래부터 차례로 소를 도와줄 수 있는 닭 리스트를 돌며, 가능하다면 바로 닭을 할당해주고, bool chk 배열에 닭을 할당했다고, 표시해준다. 

- 모든 소들을 이런 방법으로 시도해본다.

 

*틀린 이유 : 닭이 입력되는 순서대로 리스트에 넣었고, 닭이 입력되는 순서에 따라 최적값이 나오지 않는 반례가 존재했다. 즉, 닭의 순서도 함께 고려해주어야 한다. 하나의 리스트안에 있는 닭들 중에서도 각각 도와줄 수 있는 소의 수가 다르다. 도와줄 수 있는 닭의 수가 여러 개라면 '도와줄 수 있는 소의 수가 가장 작은 닭'을 선택하여야 한다. 

 

바로 정답을 맞았으면, 여기서 생각이 그쳤을텐데 좀 더 문제에 대해서 분석을 해봤다.

 

2. 문제의 특징

- 답이 가질 수 있는 범위의 upper bound는 닭의 수 / lower bound는 닭 또는 소의 수이다.

 

3. 다시 시도

최적해를 구하기 위해서는 닭을 중심으로 하는 로직이 필요하다는 판단을 하였다.

 

시간 순으로 닭을 정렬한 후, 시뮬레이션하는 것처럼 해당 시간에 닭이 도와줄 수 있는 소 중

가장 급한 소를 선택하였다.

 

- '가장 급한 소' 란? 

남은 시간이 최소로 남은 소를 뜻한다. 

 

그러기 위해서 소를 B값을 기준으로 오름차순으로 정렬해주었다.

 

- 왜 남은 시간이 많은 소는 우선순위에서 밀릴까?

남은 시간이 많은 소는 뒤에 오는 닭이 도와줄 수 있는 여지가 있지만, 가장 급한 소는 현재 닭이 아니면 구해줄 수 없기 때문이다.

 

 

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#define endl    '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
struct tt {
    int l, r;
};
vector<tt> cow;
 
bool cmp1(const tt &a, const tt &b) {
    if(a.r != b.r) return a.r < b.r;
    return a.l < b.l;
}
 
vector<int> chicken;
int c, n;
bool chk_cow[20001];
 
int main() {
    FastIO;
 
    cin >> c >> n;
    chicken.resize(c);
    for (int i = 0; i < c; i++)
        cin >> chicken[i];
 
    cow.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> cow[i].l >> cow[i].r;
    }
    // 대체제가 적으면 바로 매칭을 시켜주자.
    // 누구와 매칭을 시켜주느냐가 관건.
    // 답의 upper bound는 닭의 수
    // lower bound는 소 또는 닭의 수
 
    sort(cow.begin(), cow.end(), cmp1);
    sort(chicken.begin(), chicken.end());
    int ans = 0;
 
    for (int i = 0; i < c; i++) {
 
        int l = -1, r = n - 1;
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            if (cow[m].r < chicken[i]) l = m;
            else r = m;
        }
 
        // target 보다 전부 크거나 / 전부 작거나 / target 위 아래 값이 적어도 하나 존재
        // 1. 전부 클 경우 : r = 0 ; arr[r] > target
        // 2. 전부 작을 경우 : r = n - 1 ;  arr[r] < target
        // 3. other : r = (idx) ; arr[r] >= target 을 항상 만족
        if (cow[r].r < chicken[i]) continue;
 
        while (r < n && (cow[r].l > chicken[i] || chk_cow[r])) r += 1;
        if (r == n) continue;
        chk_cow[r] = true;
        ans += 1;
    }
 
    cout << ans;
}