codingismylife   1년 전

아이디어는 맞게 떠올렸는데, 특정 구간에서 값을 더해줄 때 O(N)이 걸리는 것 때문에 큰 데이터에서는 데이터가 출력되지 않아서 방법을 찾던 중에 

차분 배열 트릭이라는 것을 찾았고 써서 정답을 받았습니다

이 문제는 차분 배열(값 누적해서 한 번에 더하기)말고는 무조건 시간 초과가 발생할 수밖에 없는지 궁금합니다 

항상 이런 문제 풀 때는 직접 구간에 있는 값마다 일일이 더해줬는데 이 문제는 크기가 커서 그렇게 안되는 것 같습니다...

oh040411   1년 전

강의실 배정과 비슷한 아이디어로 장애물들을 높이순으로 정렬한 후 우선순위 큐를 이용해서 풀 수도 있습니다.

또한 플레 수준의 알고리즘이긴 하지만 느리게 갱신되는 세그먼트 트리를 이용하면 O(N log H) 정도에 정답을 받을 수 있습니다.

그래도 차분 배열을 사용하는 것이 가장 간단한 것 같습니다.

codingismylife   1년 전

감사합니다 값 정렬해서 최솟값 개수 구하는 거 보고 이분 탐색이랑 누적 합 문제인 것은 떠올렸지만, 누적합 시에 일일이 더하는 것을 피하는 아이디어를 떠올리지 못해 차분 배열이라는 것을 새롭게 알게 되었네요 ㅋㅋ 다양한 방법으로 풀어봐야겠습니다!!

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