글 읽기 - 이 논리가 왜 잘못된 것일까요?

enterboj 3년 전 0

제가 생각한 방법은 안테나의 위치를 A에서 A+1로 옮기면, 현재 총 거리에서 1부터 A에 위치한 집들에서의 거리는 1씩 늘어나고, A+1부터 100000에 있는 집들에서의 거리는 1씩 줄어들어서 이에 맞춰서 총 거리를 조절하면 되겠다 싶어서 이렇게 짰습니다만 오답으로 처리됩니다. 혹시 반례가 어떤 건지 알 수 있을까요? 제가 생각해 낸 테스트케이스들에 한해서는 전부 옳다고 생각됩니다...

from collections import Counter

INF = int(1e9)

n = int(input())
houses = list(map(int, input().split()))
counter = Counter(houses)

count = 0
total_dist = sum(houses)
min_total_dist = INF
result_pos = 1
for pos in range(1, 100001):
    total_dist += count
    total_dist -= n - count
    if min_total_dist > total_dist:
        min_total_dist = total_dist
        result_pos = pos
    else:
        break
    count += counter[pos]

print(result_pos)

sait2000 3년 전 3

INF가 너무 작습니다

1에 10만 채 100000에 10만 채 있으면 최소거리가 한 10^10쯤 나오는 거 같습니다.

논리적으로 가장 간단한 해결책은11번 줄을 그냥 min_total_dist = total_dist로 바꾸면 좋을 거 같습니다

enterboj 3년 전 0

정말 감사드립니다 ㅠㅠ

이 생각 자체가 잘못된점이 있는가만 고민했지 그부분은 전혀 생각도 못하고 있었어요!

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

문제

문제

출처

ICPC

이 논리가 왜 잘못된 것일까요?

enterboj 3년 전 0

sait2000 3년 전 3

enterboj 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말