kysu5095   1년 전

set자료구조를 사용하여 해당열에 벽이나 돌들의 위치(행)을 저장해 주었습니다.

함수로 열(x)의 정보가 들어오면 해당 열의 set을 확인하여 돌을 떨구던가 좌우로 옮겨주었습니다.

이때 upper_bound를 사용하여 현재 행보다 아래있으면서(값이 크면서) 가장 가까운 값을 찾아주었는데

이 작업이 logn이 걸려서 저는 제 알고리즘이 logn이라고 생각했습니다.

해당열에 돌이나 벽이 30만개를 거의 다 채워도 금방 돌의 위치를 알 수 있다고 생각하는데

시간초과가 나버리네요ㅠ 어떤 문제점이 있는건가요?

sait2000   1년 전

while 문의 도는 횟수를 보장할 수가 없습니다. 아래처럼 계단(?)이 좌우로 왔다갔다 하는 모양이면 while문이 총 R^2번 쯤 도는 데이터가 생길 겁니다

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