shadowpur97   1년 전

25 퍼 정도에서 메모리 초과가 자꾸 뜨는데 원인을 모르겠네요.. ㅠㅠ

최소 높이를 저장하는 세그먼트 트리로 풀었습니다!

lighthouse97   1년 전

main()의 while 문내에 height와 segmnt 배열을 동적으로 할당해서 사용해 보세요. 사용이 끝나면 새로 할당하기 전에 제거하구요.

그리고 segmnt 배열의 크기가 잘못되어 있읍니다. N의 2배로 할당하면 필요한 만큼 할당할 수 없는 경우도 생깁니다.

byeongkeunahn   1년 전

lighthouse97님이 말씀해주신 부분이 맞습니다. 하지만 한 군데가 더 틀렸습니다. 그 외에는 틀린 곳은 없는 것 같습니다. 정리하면 다음과 같습니다.

  • 세그먼트 트리는 원소 수 N의 4배로 한다고 기억하시면 됩니다. 즉, 73번 줄의 선언을 int segmnt[N << 2]로 바꿔야 합니다.
  • 51번 줄에서 정수 오버플로우가 발생합니다. 저장은 64비트형에 하지만 중간 계산 시 32비트 곱하기 32비트여서 이미 오버플로우가 발생한 이후에 sign extension을 하여 64비트로 늘려봐야 소용이 없습니다. height[temp] * (ll)(end - start + 1)처럼 바꿔야 합니다.

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