hui   1년 전

전봇대 간격이 k 일때 이동거리의 합을 반복문으로 구하는 함수 f 를 정의해서

그때그때 함숫값을 찾는데, 이점이 비효율적이여서 그런것 같기도 하고,, 아니면 그냥 파이썬 자체의 문제인지 궁금합니다

삼분 탐색으로 함수 f의 최솟값을 찾고 있습니다

kwakws0627   1년 전

1. 빠른 입출력 사용해보세요.

빠른 입출력 관련 내용은 아래 문제 참고하세요.

https://www.acmicpc.net/proble...

 

2. 17번째 while 문 블록 안에서 불필요한 계산을 하고 있습니다.

f(x), f(y) 값은 20번째 줄에서 이미 구했습니다.

하지만 23번째 줄, 26번째 줄 그리고 29번째 줄에서도 이미 구한 값들을 계속 다시 구하고 있습니다.

 

3. 삼분 탐색 조건이 이상합니다.

아래 반례 확인해주세요.

아래 반례 넣으면 무한루프에 빠집니다.

아래 반례에서는 x가 4, 5,6 일 때 f(x)의 값 6으로 같습니다.

그러므로 abs(right - left) <= 1 이란 조건으로 절대 들어가지 못합니다. (left = 4, right = 6인 상태로 무한루프 돕니다)

올바른 삼분 탐색 조건은 구글 검색 등으로 찾아보세요.

(혹은 이분탐색으로도 풀 수 있습니다. 이분탐색 풀이도 생각해보세요.)

 

(추가) 모두 올바르게 고쳐도 계속 시간초과 뜨면 

python 말고 pypy로 제출해보세요.

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