반례입니다.
34081번 - 흰수염과 해적들
아직 이 문제를 풀어보지도 않았고 제가 제시한 반례가 맞는 반례일지도 확실하지는 않아요.
하지만 다음 테스트케이스가 도움이 될 것 같아 올려봅니다.
제가 지문을 읽고 테스트케이스에 적용해본다면
(0, 5)와 원점 사이 거리가 L=5보다 작거나 같으니까 400 먹기
남은 해적들은 (0, 0)에서 멀어지는 쪽으로 이동하기
(다시 말해, (0,2)에 있던 해적은 (0, 3)으로, (0, 3)에 있던 해적은 (0, 4)로, (0, 4)에 있던 해적은 (0, 5)로, (0, 6)에 있던 해적은 (0, 7)로)
그 다음 (0, 5)에 있던 해적 퇴치하고 600 먹기
이런 식으로 반복하다 보면 1000, 800, 600, 400 현상금을 먹으니까 2800이 될 거라 생각을 했어요.
근데 코드 결과는 1800이 나오더라고요.
제 생각이 맞는지 궁금합니다.
다들 정말 감사드립니다. 열심히 하겠습니다.
고수분들 질문이 있습니다.
문제 설명에 그리디 알고리즘 태그가 있는데
만약
흰수염으로 부터 거리 올림한 값 : 4 현상금: 3
흰수염으로 부터 거리 올림한 값 : 3 현상금 : 8,9
흰수염으로 부터 거리 올림한 값 : 2 현상금 : 911,912
같은 입력이 있을 때에는 뭘 기준으로 그리디를 진행해야하나요?
아까 전에 코드 작성한 걸 보고 반례를 또 찾아오긴 했습니다.
해결하실 수 있을 겁니다.
그리고 제가 '반례를 남기고 갑니다'라는 글에서 sqrtl, ceill을 쓰라고 강력하게 권장했던 것 같은데,
여기서 (long long)으로 형변환하는 게 좋을 거에요.
왜냐하면 priority queue에는 long long을 집어넣으니까요.
행운을 빕니다.
댓글을 작성하려면 로그인해야 합니다.
outsidercat 9달 전
제한 범위를 초과하는 입력값도 잘 처리하는것 같은데 왜 WA를 받는지 모르겠습니다.
제발 도와주세요.