글 읽기 - 반례를 못 찾겠습니다..

woghks7788 2년 전 0

접근 방식 자체가 잘못된 건지 게시판에 나온 반례는 다 해본 거 같은데 계속 틀리네요

이분 탐색을 이용하려 했는데 올바르게 사용하지 못하고 있는 거 같습니다

고수님들 조언 부탁드립니다..

import sys
N, C = list(map(int, input().split()))
T = [int(sys.stdin.readline()) for _ in range(N)]
T.sort()

max_num = max(T)
min_num = min(T)

gap = (max_num+min_num) // 2
while min_num <= max_num:
    count = 0
    last = 0
    for i in range(N):
        if i == 0 or T[i] - last >= gap:
            count += 1
            last = T[i]

    if count < C:
        max_num = gap-1
    elif count >= C:
        min_num = gap+1
    gap = (max_num+min_num) // 2

print(gap)

tong39 2년 전 3

반례입니다.

input)

4 3

ans = 2(3개를 어떻게 선택해도 가장 인접한 두 공유기 사이의 거리는 같음)

output : 10

woghks7788 2년 전 1

답변 감사드립니다 :)

좀 더 고민해보겠습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 못 찾겠습니다..

woghks7788 2년 전 0

tong39 2년 전 3

woghks7788 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말