Algorithm (PS)

[백준] 28305번: 세미나 배정 (Python/파이썬)

minjiwoo 2023. 7. 23. 12:49
728x90

 

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

 

28305번: 세미나 배정

DEVOCEAN은 SK그룹의 대표 개발자 커뮤니티이자, 내/외부 개발자 간 소통과 성장을 위한 플랫폼이다. DEVOCEAN의 콘텐츠로는 SK 개발자들이 직접 작성한 최신 개발 관련 글과 기술을 공유하고, 테크뉴

www.acmicpc.net

위의 문제인데... 참고할 문제로는 강의실 배정, 공유기 설치 문제가 있다. 

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

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

www.acmicpc.net

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

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

 

이분탐색을 진행하되, 이분탐색의 기준이 되는 값을 계산해주어야 한다 

# https://www.acmicpc.net/problem/28305

n, t = map(int, input().split())
array = list(map(int, input().split())) # 반드시 세미나 하는 날 (외부 세미나)
array.sort()  # 3 4 5 6 7
dp = [0] * 200001

def calc(num):
    for i in range(n):
        dp[i] = array[i]

    if num == 0:
        return False
    for i in range(n):
        if i < num:
            if dp[i] >= t: # 연속
                dp[i] = array[i] + 1
            else:
                dp[i] = t + 1
        else:
            if dp[i-num] > array[i]:
                return False
            if dp[i-num] + t <= array[i] + 1:
                dp[i] = array[i] + 1
            else:
                dp[i] = dp[i - num] + t

    return True

def binary_search():
    left = 1
    right = 200000
    mid = (left+right) // 2
    while left < right:
        if calc(mid):
            right = mid - 1
        else:
            left = mid + 1
        mid = (left + right) // 2
    if not calc(mid):
        mid += 1
    return mid


print(binary_search())
728x90