kimdozzi   2년 전

NM이 최대 10^6이고, HW도 최대 10^6입니다. 그래서 당연히 틀리겠지? 했지만 HW가 커지면 커질수록 NM의 최대 범위만큼 BFS가 돌지 않을 수도 있지 않을까?라는 생각에 완탐을 시도했고 정답으로 결과가 나왔습니다..... 2900ms로 통과했구요. 왜 맞았는지 모르겠어요. 왜 통과한건가요? 시간복잡도를 알려주실 분 계실까요...

doju   2년 전

직사각형이 놓일 수 있는 위치는 총 (N - H + 1)×(M - W + 1)곳이고, 매 위치마다 직사각형이 덮는 H×W개의 칸을 일일이 확인하므로 총 연산 횟수는 둘의 곱, 즉 (N - H + 1)×(M - W + 1)×H×W에 비례할 것입니다. 이 식의 값은 N = M = 1000, H = W = 500일 때 627.5억에 달하므로, 실제로는 문제를 해결하기에 지나치게 느린 풀이입니다.
해당 데이터를 추가 요청했습니다.

kimdozzi   2년 전

역시나 말도 안되는 풀이였군요 ㅎㅎ


답변 감사합니다. 

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