글 읽기 - [파이썬] 반례를 찾아주세요

sonok 2년 전 0

s_length는 N기준 최대로 자를 수 있는 길이고

gap 은 이분탐색을 위한 변수입니다

첫 while 문에서 gap을 2로 나누며 이분탐색을 진행해 N개로 나눌 수 있는 length를 찾고

두번째 for문을 통해 N개로 나눌 수 있는 최대 length를 찾습니다.

첫 while문에서 N으로 나눌 수 있는 length를 못 찾은 것일까요?

반례를 모르겠습니다..!

import sys
K, N = map(int, sys.stdin.readline().split())

Lan_cables = [int(sys.stdin.readline()) for _ in range(K)]

s_length = sum(Lan_cables) // N
length = s_length
gap = s_length // 2

while gap:
    count = 0
    for cable in Lan_cables:
        count += cable // length
    
    if count > N:
        length += gap
    elif count < N:
        length -= gap
    else:
        break
    
    gap //= 2

for leng in range(length, s_length+1):
    count = 0
    for cable in Lan_cables:
        count += cable // leng
    if count < N:
        print(leng-1)
        break
else:
    print(s_length)

314programs 2년 전 1

반례:

출력: 1444

답: 1443

다른 케이스도 미세한 차이가 나요.

sonok 2년 전 1

와아 정말 감사드립니다.
어떻게 이런 반례들을 찾으시는지 ㅠㅠ 고맙읍디다..

확인해보니 gap이 0에 조기수렴함에따라 나온 문제였고

고치니 시간초과가 나기에 첫 while문에서 한번에 찾아내는 방식으로 해결했습니다.

감사합니다!

314programs 2년 전 3

한글실력이 떨어지니 이헤 바랍니다.

저는 반례 만들때 파이썬에서 random 모듈을 써요.

그걸로 숫자를 랜덤으로 생성후, 맞은 저에 코드와 sonok님에 코드에 입력합니다.

입력을 하나하나 하지는 않고, while을 돌려서 두 코드에 출력이 다를때까지 반복합니다.

반례 만드는 코드 예제입니다: https://www.acmicpc.net/board/...

min0709 2년 전 0

혹시 랜덤한 값을 넣은게 옳은 답이 무엇인지는 어떻게 아시나요?

314programs 2년 전 0

이미 맞은 제 코드에 랜덤한 값을 넣어요.

맞았다고 판정이된 코드니까 문제에 제한을 지키는 랜덤한 값을 넣으면 답이 맞아요.

min0709 2년 전 1

감사합니다!

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

문제

문제

출처

ICPC

[파이썬] 반례를 찾아주세요

sonok 2년 전 0

314programs 2년 전 1

sonok 2년 전 1

314programs 2년 전 3

min0709 2년 전 0

314programs 2년 전 0

min0709 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말