wjddms206   2년 전

도저히 이유를 모르겠습니다..


저의 방법은 0~15000사이의 값으로 이분탐색하며 최적화된 연료를 찾습니다.

bfs() 함수는 
(0,0)에서 시작하여 모든 점의 거리를 확인해가면서 파라미터인 oil 값 내에서 해결이 되면 queue에 넣고 마지막(10000, 10000)까지 도착할수 있는지 확인합니다. 
도착하면 true반환, 아니면 false반환합니다.
true를 반환하면 이분탐색하는 부분에서 더 낮은 숫자의 연료가 사용될 수 있는지 알아보고,
false를 반환하면 더 높은 연료를 넣고 다시 확인합니다.

거리를 구하는 공식은 루트를 씌워야 하기 때문에 비교 차체를 제곱한 값으로 했습니다.

portableangel   2년 전

거리의 합들의 제곱 != 거리의 제곱들의 합 이라는 점을 간과하신 것 같습니다.

wjddms206   2년 전

친절하시고 빠른 답변 감사합니다. 

그러나 잘 이해가 안갑니다... ㅠㅠㅠㅠㅠㅠ

11.png이게 아니라는 말씀이신가요??? 

첫번째 줄이 성립되지 않나요??

xowns9418   2년 전

오졋다링~~

portableangel   2년 전

말이 좀 이상하게 됐네요.. 예를 들어 거리가 45인 경우, 실제로는 4의 연료가 필요하고 이를 제곱하면 16이 되어야 하지만 현재 코드는 20이 필요하다고 할 것ㅅ 같습니다.

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