BOJ 15823 카드 팩 구매하기

카드 팩 구매하기
(http://boj.kr/15823)

이분탐색 간단한 문제들도 이분탐색인줄도 모르고, 알아도 답을 어떻게 체크할지 몰라서 못 풀때가 많았는데 왠지 이건 바로 떠올랐다. 쉬운 편인가?

카드 팩에 들어갈 카드 수를 기준으로 이분탐색한다.
넣을 카드 수를 정했으면, 가능한지를 확인해야 한다. 우선, 왼쪽이나 오른쪽부터 봤을 때 카드팩을 만들 수 있으면 만드는 것이 무조건 이득이다.
그러므로, 슬라이딩 윈도우의 느낌으로 카드팩을 만들 수 있는지 확인한다.
각 수가 등장한 위치를 체크해두고, 그 수가 또 등장했을 때 현재 카드팩 안에 있다면 그 뒤부터 카드팩을 만들면 된다. 개수를 채웠다면, 그 다음부터 카드팩을 만든다.
이해가 안 되면 코드를 보는게 나을 수도 있다.

#include <bits/stdc++.h>
 
int card[100001], chk[500001];
 
int main() {
    int n, m;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 1;i <= n;++i)
        scanf("%d", &card[i]);
 
    int left = 1, right = n, ans = 1;
    while (left <= right) {
        int mid = (left + right) / 2, cnt = 0, s = 1;
 
        memset(chk, 0, sizeof(chk));
        for (int i = 1;i <= n;++i) {
            if (chk[card[i]] > 0 && chk[card[i]] >= s) 
                s = chk[card[i]] + 1;
            chk[card[i]] = i;
            if (i - s + 1 == mid) {
                cnt++;
                s = i + 1;
      }
            if (cnt == m)
                break;
        }
        if (cnt == m) {
            ans = std::max(ans, mid);
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}