(백준 2613 숫자구슬

• tags : (algorithm

  No matching post could be found

  - (binary search
• 문제 링크 : https://www.acmicpc.net/problem/2613
• 풀이 링크
  • Python

• 하나의 구간을 특정 갯수로 분할하는 문제
• 구간별 최소합을 구해야하는데, 그 범위가 넓어서 이분탐색을 활용해야한다.
• 그리고 두가지 유의사항이 있는데,
  • 각 구간에 넣을 수 있는 구슬 숫자와 합을 잘 확인해야 하고,
  • 모든 구간에 하나 이상의 구슬이 들어가야 한다.

left, right = 0, sum(beads)
max_bead = max(beads)
ans = right
beads_count = []
while left <= right:
    mid = (left + right) // 2
    if mid < max_bead:
        left = mid + 1
        continue
    counts = get_beads_counts(M, mid, beads)
    if counts:
        ans = mid
        beads_count = counts[::]
        right = mid - 1
    else:
        left = mid + 1

• 기본적인 이분탐색 구성은 다음과 같이 했다.
  • 우선, left값을 max(beads)로 설정했으면 더욱 좋았을 듯 하다.
• left, right값을 기준으로 mid값을 설정, 해당 갯수를 각 구간의 최솟값으로 설정할 수 있는지 확인한다.
• mid값으로 각 구간을 분할할 수 있는지는 아래와 같이 확인한다.

counts = [0] * divide
idx = count = 0
sum_now = 0
for x in beads:
    if sum_now + x > max_sum:
        counts[idx] = count
        idx += 1
        count = 0
        sum_now = 0
    if idx == divide:
        return []
    sum_now += x
    count += 1
counts[idx] = count
left = idx
idx += 1

• 우선 원하는 구간으로 나누는 후, 앞에서부터 최대한 채워넣는다.
  • 구슬의 값을 하나씩 확인하며 구간합을 구하고,
  • 구간합이 원하는 값 mid보다 커지기 전에 각 구간에 구슬 갯수를 입력한다.
  • 모두 순회하고 남은 값도 처리한다.

while idx < divide:
    if counts[left] > 1:
        counts[left] -= 1
        counts[idx] += 1
        idx += 1
    else:
        left -= 1

• 각 구간에 구슬이 하나 이상 있어야 하는 조건을 해결하기 위해 이 부분을 작성했다.
  • 비어있는 위치마다 하나씩 구슬을 뒤로 밀어주는 방식으로 해결했다.