hyperion1019   5년 전

갈 수 있는 점중 가장 끝의 점을 b로 놓고, 갈 수 있는 범위에서는 가장 연료가 많은 주유소만 간다고 가정해서 간 주유소의 기름을 그대로 b에 더하는 방법으로 접근했는데 계속 틀렸다고 뜹니다. 반례 좀 찾아주세요 ㅠㅠ

dladydwo123   5년 전

2
2 3
4 7
14 4

이 반례가 될수 있을 것 같습니다.

2,4을 모두 방문할 시엔 도착지점에 갈 수 있지만, 질문자 님이 작성하신 코드는 4만 방문 함으로, 14까지 도달할 수 없어서 -1을 출력합니다.

hyperion1019   5년 전

진짜 감사합니다!!

hyperion1019   5년 전

말씀하신 부분 고쳐서 24번째 줄의 if(Q.empty())를 if(Q.empty()&&P.empty())으로 바꿨는데도 틀렸다고 뜨네요... 혹시 다른 부분에서 또 틀린점이 있나요?

dladydwo123   5년 전

Q가 우선순위 큐라서 24번째 줄을 &&P.empty()을 추가 했다하더라도 근본적인 것은 바뀌지 않은것 같습니다.

제가 앞에서 써드렷던 반례에서 중요한점은 4지점과 2지점을 동시에 고려해야 된다는 것인데 질문자님의 코드는 그부분을 고려치않은 것으로 보입니다.

우선순위 큐에 주유소 정보를 넣음 으로서, 처음 발견하는 것은 4지점이고, 이부분이 가는것이 불가능 하면 2지점을 가야하는데, 질문자님의 코드는 4지점을 발견하고 못가니까 그냥 종료해버립니다. 


어디까지나 제 생각입니다. 틀릴 수도 있다는 점을 알아주세요 

hyperion1019   5년 전

답변 정말 감사합니다. 정말 많은 도움이 되었어요.

하지만 지적해주신 부분은 24번째 줄에 &&P.empty()을 추가함으로써 들르지 않고 지나쳐온 주유소가 있을 경우 거기에서도 기름을 받았다고 가정하여 해결된 것 같습니다. 실제로 제시해주신 반례를 입력해보았을 때도 별 문제가 없이 작동했고요. 아마 다른 부분에서 반례가 또 있는 모양입니다....

지적해주신 반례 정말 큰 도움이 되었습니다. 다시한번 감사드려요 ㅠㅠ

hyperion1019   5년 전

와...정말 어이없는거를 실수했네요 ㅠㅠ 답변자님께서 지적해주신 부분만 고치면 완성되는 코드였습니다!! 진짜진짜 감사합니다!!

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