gunwooyeon   4년 전

분할 정복을 통하여 mid 양 사이드 최소 길이를 구하고,

mid가 처리가 되지 않았기 때문에, 전체 배열을 돌며, mid 인덱스를 제외하고 길이를 구하여 분할정복에서 구한 ans와 비교하여

최솟값을 답으로 출력하게 했는데, 왜 틀린지 알고 싶습니다.

chogahui05   4년 전

point x ~ point y까지의 점 쌍 중에서 최단 거리를 가지는 쌍 (a,b)를 찾으세요 할 때..

mid점을 하나 뒀네요. (x~mid) (mid+1,y)

일단 x~mid까지 최단 점쌍 + mid+1 ~ y까지 최단 점쌍 구해서 최소치 구하는 것까진 맞습니다.


한 친구는 (x~mid) 중에 하나에 포함되고, 다른 친구가 (mid+1 ~ y)에 포함된다고 쳤을 때

이런 조건을 만족하는 점쌍 중에서

mid, uu (단 uu는 mid+1 ~ y사이에 있는 점 중 하나)가 최단 거리 점쌍이 된다는 보장이 있나요?


예를 들어서, 이런 경우를 생각해 봅시다.

1 1 <== x

1 3

1 5

1 1000000 <== mid

2 2

2 3

2 4 <== y

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