kth990303   3년 전

먼저 아래 코드를 시도하기 전, 플로이드를 이용한 그래프이론 및 탐색으로 문제를 해결하였습니다.

그런데, 그래프탐색을 할 필요 없이 맨해튼거리가 짧은 순으로 편의점+페스티벌 지점을 쫙 정렬한 후,

거리가 1000 이하인 곳으로 계속 이동하며 페스티벌에 도착할 수 있으면 happy, 아니면 sad를 띄워주면 되겠다 싶어서 아래와 같이 코드를 작성해보았는데, WA를 받네요.

제가 생각하기엔 정렬을 저렇게 한다고 무조건적으로 맨해튼 거리가 짧은 순 정렬이 아니지 않을까 싶긴한데 (11~13번째 줄대로 정렬해서 그리디적으로 해결하는 방법이 알고리즘이 잘못됐을 확률이 높을 것 같은데) 딱히 반례가 생각나지 않고, 코드가 틀린 이유를 명확히 집기 어렵네요.

아래와 같은 그리디+정렬 코드는 왜 WA를 받나요?

yooase12   3년 전

맨해튼 거리 짧은순이 first+second합이면

1

2

0 500

-1000 1000

1000 500

1000 1500

일때

0과 1500이니 위 순서대로 정렬이 될테고

여기서 첫번째꺼 계산할때 거리가 1000초과하므로 sad가 나오게 될것입니다.

kth990303   3년 전

@yooase12

그렇네요 좌표값이 음수가 가능하군요 명쾌한 답변 감사합니다

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