outsidercat   9달 전

제한 범위를 초과하는 입력값도 잘 처리하는것 같은데 왜 WA를 받는지 모르겠습니다.

제발 도와주세요.

oh040411   9달 전

반례입니다.

hemisphere1357   9달 전

아직 이 문제를 풀어보지도 않았고 제가 제시한 반례가 맞는 반례일지도 확실하지는 않아요.

하지만 다음 테스트케이스가 도움이 될 것 같아 올려봅니다.

제가 지문을 읽고 테스트케이스에 적용해본다면

(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이 나오더라고요.

제 생각이 맞는지 궁금합니다.

outsidercat   9달 전

다들 정말 감사드립니다. 열심히 하겠습니다.

outsidercat   9달 전

고수분들 질문이 있습니다.

문제 설명에 그리디 알고리즘 태그가 있는데

만약

흰수염으로 부터 거리 올림한 값 : 4 현상금: 3

흰수염으로 부터 거리 올림한 값 : 3 현상금 : 8,9

흰수염으로 부터 거리 올림한 값 : 2 현상금 : 911,912

같은 입력이 있을 때에는 뭘 기준으로 그리디를 진행해야하나요?

oh040411   9달 전

흰수염과의 거리보다 반지름 L인 원까지의 거리가 더 중요합니다. 거리가 L보다 멀어지기까지 걸리는 시간을 계산해 놓고, 이 제한시간과 현상금을 잘 고려해서 골라야 합니다. 어떤 해적의 제한 시간이 t라면 그 해적을 잡으려면 반드시 t턴 안에 골라야 한다는 것에 주목해보세요

hemisphere1357   9달 전

아까 전에 코드 작성한 걸 보고 반례를 또 찾아오긴 했습니다.

해결하실 수 있을 겁니다.

그리고 제가 '반례를 남기고 갑니다'라는 글에서 sqrtl, ceill을 쓰라고 강력하게 권장했던 것 같은데,

여기서 (long long)으로 형변환하는 게 좋을 거에요.

왜냐하면 priority queue에는 long long을 집어넣으니까요.

행운을 빕니다.

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