글 읽기 - 반례를 찾아주세요..ㅠㅠ

antk7894 2년 전 0

시간 초과가 나는 코드인 것은 알고 있습니다,,

근데 pypy3로 정답을 제출했을 때 시간 초과가 아닌 틀렸습니다 가 나오더라구요

시간 초과로도 틀렸습니다 가 나올 수 있나요??

아니라면 제 코드의 반례를 알려주실 수 있을까요,,,

감사합니다!

import sys

# 입력 받기
n, c = map(int, sys.stdin.readline().rstrip().split())
home = []
for _ in range(n):
  home.append(int(sys.stdin.readline().rstrip()))

# 집 위치 정렬
home.sort()

# 설치할 공유기가 두 대인 경우
if c == 2:
  print(home[-1] - home[0])
else:
  # 집들 간 거리 배열
  dist = []
  for i in range(len(home) - 1):
    dist.append(home[i + 1] - home[i])

  # 거리들 뭉치기
  for _ in range(n - c):
    min_index = dist.index(min(dist))
    if min_index == 0:
      second_index = 1
    elif min_index == len(dist) - 1:
      second_index = len(dist) - 2
    else:
      second_index = min_index + 1 if dist[min_index - 1] > dist[min_index + 1] else min_index - 1
    dist[min_index] += dist[second_index]
    del dist[second_index]

  # 정답 출력
  print(min(dist))

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

문제

문제

출처

ICPC

반례를 찾아주세요..ㅠㅠ

antk7894 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말