백준 15823 - 카드 팩 구매하기

소스 코드(C++) : https://github.com/CaChiJ/JustCodes/blob/main/Algorithm%20Solutions/Binary%20Search/BOJ15823.cpp

---

👀 살펴보기

문제의 설명을 보자. 설명이 긴 관계로 이 글에 별도로 설명을 삽입하지는 않겠다.

한 카드팩에 들어가는 카드 수량을 ${K}$라고 하자. ${K}$를 1,2,3, ... 으로 늘려나가며 ${M}$개를 구성할 수 있는지 확인하려면 총 ${N}$회 확인해야 한다. 임의의 ${K}$에 대해 ${M}$개의 카드팩을 구성할 수 있는지 확인하려면 ${O(N)}$의 시간복잡도가 필요하다. ${N}$은 최대 100,000이므로 ${O(N^2)}$인 이 방법으로는 시간 초과가 발생한다.

1. 두 부분으로 나눠지네?

임의의 ${K}$(한 카드팩에 들어가는 카드 수량)에 대해 ${M}$개의 카드팩을 구성할 수 있는지 판별하는 결정 문제로 바꿔보자. 그 결과를 일반화하여 그림으로 표현해보면 다음과 같다.

가로축: ${K}$(오른쪽에 위치할수록 크다)
파랑: ${M}$개의 카드팩을 구성할 수 있음
빨강: ${M}$개의 카드팩을 구성할 수 없음

그림에서 이 문제의 답(하나의 카드 팩에 구성할 수 있는 카드의 최대 수량)은 파랑과 빨강의 경계에 위치한 파란색 칸의 ${K}$값이다. 이 성질을 이용하면 Parametric Search를 이용해
${O(logN)}$개의 임의의 ${K}$에 대해 결정 문제를 풂으로써 답을 찾을 수 있다.

2. 결정 문제는 어떻게 푸는데?

가장 먼저 떠오르는 방법은 모든 카드를 순회하며 각 카드를 시작점으로 하는 카드팩을 구성해보는 것이다. 이 방법은 ${O(N^2)}$의 복잡도를 갖는다. 하지만 ${logN}$개의 결정 문제를 풀어내야 하므로 이보다 더 효율적이어야 한다. 큐의 작동방식을 이용해 ${O(N)}$ 코드를 작성할 수 있다. 자세한 내용은 아래 '🧶로직'에서 설명하겠다.

---

🧶 로직

1. 이분 탐색 구현

사실 위의 '👀살펴보기'에서 분석한 내용을 토대로 이분탐색을 구현하면 끝이다. 의사 코드를 덧붙여보자면 다음과 같다. 실제 코드는 여기에서 살펴보길 바란다.

left = (K가 될 수 있는 가장 작은 값)
right = (K가 될 수 있는 가장 큰 값)

while (left가 right보다 작을 때)
    mid = (left와 right의 평균)
    
    if (K가 mid일 때 M개의 카드팩을 구성할 수 있음)
        left = mid
    else
        right = mid - 1

2. 결정 문제 풀기

글보다 아래 의사 코드를 보는 편이 쉬울 것이다.

for (i를 0부터 N-1까지 1씩 증가시키며 아래를 반복함)
    if (i번째 카드의 식별번호가 이미 카드팩에 포함됨)
        while (큐의 첫번째 식별번호가 i번째 카드의 식별번호와 다름)
            큐의 첫번째 식별번호를 빼냄
            큐의 첫번째 식별번호가 카드팩에 포함되지 않음을 저장
        
        큐의 첫번째 식별번호(i번째 카드의 식별번호)를 빼냄
    
    큐에 i번째 카드의 식별번호를 추가함. 
    i번째 카드의 식별번호가 카드팩에 포함되어있음을 저장
    
    if (큐의 크기가 M보다 크거나 같음)
        만들어진 카드팩 개수를 1 증가시킴
        큐를 비움
        모든 식별번호가 카드팩 포함되어 있지 않다고 저장
    

---

⏱ 시간 복잡도

모든 카드는 한 번씩 큐에 들어가고 나오므로 ${O(N)}$이 걸린다. i번째 카드의 식별번호가 이미 카드팩에 포함되어 있는지 확인하거나 저장하는 작업은 배열을 이용해 ${O(1)}$에 수행할 수 있다. 각 카드에 대해 상수 횟수만큼 수행되므로 시간복잡도는 ${O(N)}$이다. 따라서 결정 문제 하나를 푸는 데 드는 시간복잡도는 ${O(N)}$이다.

${O(logN)}$개의 ${K}$에 대해 결정문제를 풀면 전체 시간복잡도는 ${O(NlogN)}$이다.

---

💊 개선점

이 글의 로직에서는 설명상의 편의를 위해 큐를 사용하여 일련번호를 저장했다. 큐의 요소들이 실제 카드의 배열에서 연속적인 일부임을 고려하면 큐를 사용하지 않고 이를 구현할 수 있다. 시작점과 끝점을 저장하는 방식으로 큐를 흉내내는 것이다. 이를 통해 메모리를 절약할 수 있다. 깃허브에 게시된 필자의 소스코드도 이런 방식으로 작성되었다.