글 읽기 - 이진탐색 right 값이 10000이면 왜 틀렸다고 뜨나요?

junman95 2년 전 1

제 코드에서 end가 right의 역할을 하는데,

end = sum(N_list) 일경우 통과하고 최대영상길이인 10000으로 설정하면 틀렸다고 뜹니다.

시간복잡도는 NlogN으로 동일한데, sum값으로 초기화 해 줄 경우 가짓수가 확연히 줄어들 케이스는 많을 듯 싶습니다.

이 문제가 맞는건가요?

동일 알고리즘 내에서도 최적화가 필요한 문제인지 궁금합니다.

from collections import deque
import sys

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


def binary():
  start = max(N_list)
  end = 10000
  res = float("INF")
      
  while start <= end:
    mid = (start + end) // 2
        
    temp = 0
    num_disk = 0
    for i in range(len(N_list)):
      temp += N_list[i]
      if temp < mid:
        pass
      elif temp == mid:
        temp = 0
        num_disk += 1
      else:
        temp = N_list[i]
        num_disk += 1
            
    if temp:
      num_disk += 1
      
    if num_disk > M:
      start = mid + 1
    else:
      end = mid - 1
      res = min(mid,res)
      
  return res

print(binary())

aru0504 2년 전 1

각 강의의 길이의 최댓값이 10,000 이하이지, 한 블루레이의 길이의 최댓값이 10,000 이하가 아닙니다

junman95 2년 전 1

aru0504

아, 그렇겠네요 ㅎㅎ 감사합니다!!

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

문제

문제

출처

ICPC

이진탐색 right 값이 10000이면 왜 틀렸다고 뜨나요?

junman95 2년 전 1

aru0504 2년 전 1

junman95 2년 전 1

aru0504

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말