글 읽기 - 파이썬 시간초과 질문입니다. 도저히 모르겠네용..

ejzl521 2년 전 0

이분탐색으로 구현했는데 왜 시간초과가 나올까요 ㅠㅠ... 입력받는 부분도 sys 모듈을 사용했는데..

import sys

N, M = map(int, sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))

left, right = 1, max(trees)
while left <= right:
    mid = (left + right) // 2
    total = 0
    for i in trees:
        if i >= mid:
            total += i - mid

    if total >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)

dldyddlwl 2년 전 1

아래에 있습니다.

2번째 방법의 경우 저도 검색해보다가 찾게 된 신기한 건데요.

https://stackoverflow.com/ques...

여기를 참조하시면 더 좋을 것 같습니다.

# 1번째 방법입니다!

import sys

N, M = map(int, sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))

left, right = 1, max(trees)
while left <= right:
    mid = (left + right) // 2
    total = 0
    for i in trees:
        if i >= mid:
            total += i - mid
        if total >= M:            # 이미 M을 넘었으면 더 루프를 돌 필요가 없으므로 빠져나감으로써 시간을 아낍니다!
            break

    if total >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)

####################################################################################

# 2번째 방법입니다.

import sys

N, M = map(int, sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))

def cal(mid):                    # 그 방법은 바로!! 함수를 이용하는 것입니다.
    total = 0
    for i in trees:
        if i>=mid:
            total+=i-mid
    return total

left, right = 1, max(trees)
while left <= right:
    mid = (left + right) // 2
    total = cal(mid)                # 같은 코드지만 함수를 사용해서 시간을 아낍니다.

    if total >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)

ny2485 2년 전 0

와......... ㅠㅠ

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

문제

문제

출처

ICPC

파이썬 시간초과 질문입니다. 도저히 모르겠네용..

ejzl521 2년 전 0

dldyddlwl 2년 전 1

ny2485 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말