글 읽기 - 그리디 방식으로는 어떤 반례가 있을까요..?

joyh1021 2년 전 0

하단의 코드처럼 사용했는데, 틀렸다는 판정이 나왔습니다. 어떤 반례가 있을까요?

아래처럼 작성한 이유는.. 문제에서 무조건 모든 동생을 찾아야 하니까, 수빈이 위치와 모든 동생의 위치를 포함해서 정렬한 다음,

임의의 두 위치 간의 가장 짧은 거리가 수빈이가 이동해야 할 값이 아닐까요?

혹시 제가 말씀드린 경우에 어긋나는 반례를 제시해준다면 너무나 감사하겠습니다 :)

import sys

input = sys.stdin.readline
n, s = map(int, input().split())
bros = list(map(int, input().split()))
bros.append(s)
bros.sort()

min_dist = int(1e9)
for i in range(0, n):
    min_dist = min(min_dist, abs(bros[i]-bros[i+1]))
print(min_dist)

djm03178 2년 전 1

다음과 같은 반례가 있습니다.

3 1
4 6 9

정답: 1
출력: 2

joyh1021 2년 전 0

빠른 답변 감사드립니다! 덕분에 이해했네요!

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

문제

문제

출처

ICPC

그리디 방식으로는 어떤 반례가 있을까요..?

joyh1021 2년 전 0

djm03178 2년 전 1

joyh1021 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말