[백준] 15732번: 도토리 숨기기(Pyhton, 이진 탐색)

문제 링크

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

15732번: 도토리 숨기기

풀이

처음엔 단순히 N(상자 개수)개의 누적합 테이블(dp)을 만들어, start, end, mid를 통해서 dp[mid]의 도토리 개수에 따라 mid를 파악하려 했다.

[시간 초과 난 코드]

import sys
input = sys.stdin.readline

N, K, D = map(int, input().split())

boxes = [0] * (N + 1)
for _ in range(K):
    a, b, c = map(int, input().split())
    for i in range(a, b + 1, c):
        boxes[i] += 1

for i in range(1, N + 1):
    boxes[i] += boxes[i-1]

start = 0
end = N
result = N + 1
while start <= end:
    mid = (start + end) // 2

    if boxes[mid] < D:
        start = mid + 1

    if boxes[mid] >= D:
        result = min(result, mid)
        end = mid - 1

print(result)

⇒ N ≤ 1000,000, K ≤ 10,000 이며, 1 ≤ C ≤ A ≤ B ≤ N 이므로

for _ in range(K):
    a, b, c = map(int, input().split())
    for i in range(a, b + 1, c):
        boxes[i] += 1

위처럼 규칙을 전부 더해주는 누적합 테이블을 만드는 것이 mid를 구할땐 빠르지만 오히려 시간 초과의 원인이었다.

이진탐색때 시간초과를 피하기 위해선 O(NlogN)의 N을 잘 선정하는 것이 중요하다.

여기서의 변수 범위를 봤을 땐, K나 N이 가능성이 있다.

• K(규칙의 수) vs N(상자의 수)
  • N: 상자의 수를 알아봤자 상자 안에 도토리 수를 알아야하는데 D의 경우 $10^9$ 이므로 포기
  • K: 규칙에 대해 일일이 도토리 수를 더하지 않고, 상자의 시작, 끝 범위, 간격 수 이 3가지를 통해 도토리의 수를 유추할 수 있으므로 K가 적합하다.
• K를 기준으로 mid(마지막 도토리를 가진 상자의 번호)를 탐색하기에 어떤 방식이 좋은지
• 상자 규칙의 끝번호(rend) < 찾고자 하는 상자의 번호(mid)
  • (rend - rstart) // step + 1 로 그 규칙까지의 총 도토리 수를 알 수 있음

이진탐색때 시간초과를 피하기 위해선 O(NlogN)의 N을 잘 선정하는 것이 중요
일일이 따지는 것이 시간초과 라면, 수식으로 할 수 없는지 알아볼 것

[해결 코드]

import sys
input = sys.stdin.readline

N, K, D = map(int, input().split())
rules = []
for _ in range(K):
    rules.append(list(map(int, input().split())))

rules.sort()
start = 0
end = N
result = N + 1
# (end - start) // step + 1
while start <= end:
    mid = (start + end) // 2
    cnt = 0
    #10 ** 4
    for rstart, rend, step in rules:
        if rstart > mid:
            continue

        if rend < mid:
            cnt += ((rend - rstart) // step + 1)

        else: # rstart < mid < rend
            cnt += ((mid - rstart) // step + 1)

    if cnt >= D:
        result = min(result, mid)
        end = mid - 1
    else:
        start = mid + 1

print(result)