cdjs의 코딩 공부방

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

1. 문제

- 초기에 통 개수 $N$과 통의 용량 $X$가 주어짐.

- 다음 줄에, $i$번째 용기에 담겨 있는 헤어에센스의 양 $C_i$가 $N$개 공백으로 나누어 주어짐.

- 통 $A, B$두개를 가져가면 $min(A+B+{X \over 2}, X)$만큼이 차 있는 통으로 바꿔줌.

- 용량이 꽉 찬 통을 최대 몇 개 만들 수 있는지 구해야 함.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

통의 개수 $N \leq 100,000$ 이므로 시간복잡도 $O(N^2)$으로는 풀이가 불가능하다는 것을 알 수 있다.

또한, 통의 용량 $X \leq 10^{18}$이므로 크기 제한에 유의하여 long long 자료형을 사용해야 한다.

당연히도, 이미 남아 있는 통 중 꽉 찬 통이 있다면 이걸 가져가서 교체할 필요는 전혀 없으므로, 우선 꽉 찬 통은 모두 빼놓고 생각하자.

일단 관찰을 위해, 처음 생각한 것은 "아무렇게나 막 교환하면 꽉 찬 통을 몇 개까지 얻을 수 있을까?" 였다.

여기서 알 수 있었던 사실은, 남아 있던 용량과 관계 없이 통 3개로 무조건 꽉 찬 통 하나를 만들 수 있다는 것이다.

통 두개를 교체하면 최소 ${X \over 2}$만큼이 통에 차고, 그 통과 다른 통을 교체하면 최소 ${X \over 2} + {X \over 2} = X$만큼 차기 때문에, 최악으로 교환해도 통 3개만 있으면 통 하나를 가득 채울 수 있다.

그렇다면, 이 문제는 "통 두 개만을 사용하여 꽉 찬 통을 만들 수 있는 최대 개수 구하기" 문제로 바뀌었다.

통 두 개로 꽉 찬 통 하나를 만들기 위해서는 각 통에 들어 있던 헤어에센스의 양의 합이 ${X \over 2}$보다 많아야 하므로,

다시 한번 문제를 추상화하면 "남아 있는 용량이 ${X \over 2}$ 이상인 통의 쌍 개수를 최대화하여라." 로 바뀐다.

이제 남아 있는 용량이 ${X \over 2}$인 통 쌍 개수를 구하는 방법을 생각해야 한다.

그리고 조금 생각해보면, 남아 있는 용량이 $X$ 미만이지만 용량이 조금 많이 남은 통 두 개를 한번에 가져가서 교체하는 것은 용량 손해가 심해 보인다.

따라서, "용량이 많이 남아 있는 통은 용량이 적게 남은 통과 교체하는 것이 좋지 않을까?" 라는 생각을 할 수 있다.

즉, 최대한 용량이 많이 남아 있는 통과 최대한 용량이 적게 남은 통들 쌍 중에서 용량의 합이 ${X \over 2}$ 이상인 통들의 쌍을 투 포인터로 그리디하게 매칭하는 것이 최적이라는 가설을 세울 수 있다.

이제부터 이를 증명해보자.

오름차순으로 정렬 이후에, 가장 왼쪽의 통의 인덱스를 $l$, (가득 찬 통을 제외한)가장 오른쪽의 통의 인덱스를 $r$이라고 하자.

그러면, $C[l] \leq C[l+1] \leq C[l+2] \leq \dots \leq C[r-1] \leq C[r] < X$가 된다.

이 때, $C[l] + C[r] < {X \over 2}$라면 $C[l]$은 그 어떤 통과 더하더라도 ${X \over 2}$ 이상이 될 수 없으므로, $C[l]$은 반드시 통 세 개로만 교환 가능하다.

또한, $C[l] + C[r] \geq {X \over 2}$인 상태에서 $(C[l], C[r])$ 쌍 대신 $(C[l+1], C[r])$ 쌍을 선택하는 것은 최적이 아닌데, 만약 $C[l] + C[r] \geq {X \over 2}, C[l] + C[r-1] < {X \over 2}, C[l+1] + C[r-1] \geq {X \over 2}$라면 $(C[l], C[r]), (C[l+1], C[r-1])$ 쌍을 고를 수 있으나 $(C[l+1]+C[r])$ 쌍을 골라 버리면 $C[l]$은 절대 사용할 수 없는 통이 되기 때문에 무조건 손해가 된다.

따라서, 배열을 정렬한 뒤에 투 포인터로 "양쪽을 합해서 ${X \over 2}$ 이상이라면 $l++, r++$, 아니면 $l++$" 이라는 단순한 투 포인터 방식으로 정답을 구할 수 있다.

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


int main() {
    ll n, x;
    ll c[100005];
    int ans = 0;
    
    cin >> n >> x;
    for (int i=0; i<n; i++) {
        cin >> c[i];
    }
    
    sort(c, c+n);
    
    int l=0, r=n-1;
    int left=0;
    while (c[r]>=x && r>=0) {
        r--;
        ans++;
    }
    while (l<=r) {
        if (l<r && c[r]+c[l]>=(x+1)/2) {
            ans++;
            l++;
            r--;
        }
        else {
            l++;
            left++;
        }
    }
    cout << ans+left/3;
    
}

5. 여담

사실 풀이 부분에서 $C[l] + C[r] \geq {X \over 2}$여야 한다고 했으나, 모든 $C[i]$는 정수로 입력되기 때문에 ${X \over 2}$에서 소수점은 아예 버려도 별로 상관이 없다.

사실 while()문 안에 l==r인 부분 예외 처리를 안해줘서 몇번 박았었는데, 다행히 빨리 찾아서 고쳤다.

아마 대회였으면 조금 더 심사숙고해서 정답을 박았겠지만... 그냥 문풀중이어서 대충 박아버리니까 좀 여러번 틀렸다.

연습 중에도 이런 습관은 좀 고쳐야겠다.