글 읽기 - [파이썬]2110번 원래 코드의 문제점에 대해서 알려주세요(정답 주의)

crookid 2년 전 0

공유기의 대수가 3개가 되었을 때 계산을 멈추기 위해서 이중 for문으로 공유기 대수 -1만큼 제한을 두었고, 공유기를 둘 때마다 count를 +1 해주고, 공유기를 둔 집에 index를 설정 해 주고 break를 해 주었습니다. 제가 생각하기에 두 코드 모두 최악의 경우 N번 실행되지만, 전자의 경우 공유기가 앞쪽에 모두 설치될 수 있다면 빠르게 빠져나올 수 있을 것이라 생각했는데 오히려 뒷 코드는 시간초과가 나질 않았습니다.

제 기존 코드의 문제점을 알려주시면 감사하겠습니다.

import sys
N, M = map(int, input().split())
house = []
house = sorted([int(sys.stdin.readline()) for _ in range(N)])
start = 1
end = house[-1]-house[0]
result = 0
while start<=end: 
  mid = (start+end)//2
  index = 0
  count = 1
""" 기존 코드(시간초과한 부분)
  for _ in range(M-1): 
    for j in range(index, len(house)):
      if (house[j] - house[index]) >= mid:
        index = j
        count +=1
        break
  if count == M:
"""
#이 부분부터 정상적으로 채점된 코드
  for j in range(len(house)):
    if (house[j] - house[index]) >= mid:
      index = j
      count +=1
  if count >= M:
#이 부분까지    
    result = mid
    start = mid+1
  else:
    end = mid-1
print(result)

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

문제

문제

출처

ICPC

[파이썬]2110번 원래 코드의 문제점에 대해서 알려주세요(정답 주의)

crookid 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말