dsm20261112   8달 전

BFS를 통해 풀면서 dp 테이블에 최솟값을 갱신하는 형태로 코드를 짜 봤는데 메모리 초과가 납니다.

혹시 문제를 풀기 위해서 코드 풀이를 대충이라도 알려주실 수 있나요?

ai에게 질문하여 봐도 잘 모르겠어서 남깁니다.

시도해 보았던 코드 첨부합니다.

user   8달 전

직접 제출해보셨나요? Python 3로 제출한 결과 메모리 초과가 아닌 "틀렸습니다"를 받습니다.

반례 하나 놓고 갑니다.

not_strober   8달 전

float 캐스팅은 부정확합니다. 문자열 파싱으로 바꾸면 AC를 받습니다.

oh040411   8달 전

정답과는 별개로, sys.setrecursionlimit(1000000)을 쓰셨는데 이것을 그대로 제출할 경우 PyPy3 기준으로 1393020 KB를 사용하게 됩니다. 이 문제는 메모리 제한 1024MB + 파이썬 메모리 보너스로 통과하긴 하지만, 제한이 512 MB만 되었어도 메모리 초과가 발생했을 것입니다. 따라서 꼭 필요한 경우가 아니라면 재귀를 사용하지 않는 코드에서 recursionlimit을 불필요하게 늘리는 것은 지양하는 것이 좋습니다.

dsm20261112   8달 전

float 캐스팅을 하면 부족한 이유가 부동소수점 오차 때문인가요?

not_strober   8달 전

네. 구체적으로는 부동소수점 표현의 지수부와 가수부로 수를 나타내는 특성 때문에 절댓값으로 253(약 9 * 1015)까지만 정확히 표현되고 그보다 큰 숫자는 오차가 발생합니다.

dsm20261112   8달 전

감사합니다 덕분에 풀었습니다! 비슷한 문제 연습해보겠습니다.

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