[백준/15823] 카드 팩 구매하기 (Python)

Problem : https://www.acmicpc.net/problem/15823

15823번: 카드 팩 구매하기

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:33:39

 

---

 

문제 설명

 

주띵이는 오프라인 카드 게임 하프 스톤을 좋아하는 평범한 대학생이다. 주띵이가 자주 방문하는 게임용품 전문점인 '카드 몬스터'에서는 개점 3주년을 기념해 카드 팩 이벤트를 진행하고 있다. 이벤트에 참여한 사람은 사장이 만든 규칙을 만족하면 한 번에 많은 카드를 저렴하게 구매할 수 있다.

 

1. N개의 카드가 한 줄로 진열되어 있으며, 카드의 자리는 바꿀 수 없다.
2. 좌/우로 연속한 카드들을 묶어 하나의 '카드 팩'을 구성할 수 있다.
3. 주띵이는 정확히 M개의 카드 팩을 구매해야 한다.
4. 각 카드 팩을 구성하는 카드의 수는 일치해야 한다.
5. 한 카드 팩안에 같은 종류의 카드가 두 장 이상 존재해서는 안 된다.
6. 하나의 카드가 여러 카드팩에 속할 수 는 없다.

 

예를 들어서 N=10이고 M=3인 경우를 가정해보자. 각 카드의 식별 번호가 차례로 10, 9, 7, 7, 9, 8, 8, 8, 2, 1 이라고 한다면, 아래와 같은 방법들로 구매할 수도 있다.

 

개점 이벤트로 인해 각 카드 팩을 구성하는 카드 수에 상관없이 항상 가격이 일정하므로, 주띵이는 최대한 많은 카드를 카드 팩으로 구성하려고 한다. 하지만 한 번 카드 팩을 구성한 이후에 수정하는 것은 가게 주인이 좋아하지 않으므로, 미리 가장 이득이 되는 방법을 설계한 후 구성하려고 한다. 주띵이를 도와주자. 주띵이가 각 카드 팩에 구성할 수 있는 최대의 카드 수는 몇 장인가?

 

 

입력 및 출력

 

입력

 

첫 줄에는 두 개의 자연수 N과 M이 공백으로 구분되어 주어진다. N은 상점에 진열된 카드의 수이며 M은 주띵이가 구매해야 할 카드 팩의 수다. 이후 두 번째 줄에는 총 N개의 나열된 카드에 대한 자연수 식별 번호가 입력으로 주어진다. 가장 왼쪽에 나열된 카드부터 오른쪽에 나열된 카드까지 실제 위치와 같은 순서로 식별 번호가 주어지며, 각 식별 번호는 공백으로 구분되어 있다.

각 카드의 식별번호는 1 이상 50만 이하의 자연수이다.

 

출력

 

이벤트의 규칙을 모두 만족하면서 주띵이가 하나의 카드 팩에 구성할 수 있는 카드의 최대 수량을 한 줄에 출력한다.

 

입력 예시

 

10 1
5 2 5 3 4 1 3 1 2 1

 

출력 예시

 

5

 

 

---

 

풀이

 

투 포인터로..풀수 있었다고..?

 

우선, 각 카드 cards[i]에 대해서, 이 카드부터 시작하여 최대로 담을 수 있는 카드팩의 길이를 저장하였다. 이는 큐로 구현이 가능하다. (O(N))

또한, 우리는 카드팩의 최대 카드 길이가 기껏해야 N // M임을 알 수 있다, (중복 x) 

따라서 매개 변수 이분 탐색으로, mid길이의 카드팩이 M개 이상 등장할 수 있는지 여부를 체크하기 위해 dp를 사용하였다. dp 체크에 O(N), 매개변수 이분탐색에 O(log(N // M)) 시간복잡도가 소요되므로 총 시간복잡도는 O(Nlog(N // M))이 된다.

 

 

풀이 코드

from collections import deque

N, M = map(int, input().split())
cards = list(map(int, input().split()))

q = deque()
visited = set()
max_len = [0]*N
for i, c in enumerate(cards) :
  q.append((c, i))
  if c not in visited :
    visited.add(c)
    continue
  while q :
    _c, j = q.popleft()
    max_len[j] = i - j
    if _c == c :
      break
    visited.discard(_c)
while q :
  _c, j = q.popleft()
  max_len[j] = N - j

def calculate(length) :
  dp = [0]*(N+1)
  for i in range(N) :
    if max_len[i] >= length :
      dp[i+length] = max(dp[i+length], dp[i] + 1)
    dp[i+1] = max(dp[i], dp[i+1])
  return dp[-1] >= M

def bisect() :
  start, end = 1, N // M + 1
  ret = 0
  while start < end :
    mid = (start + end) // 2
    if calculate(mid) :
      ret = mid
      start = mid + 1
    else :
      end = mid
  print(ret)

bisect()

풀이 완료!