snrnsidy   2년 전

해당 문제 출제자입니다.

제가 문제를 출제하기 전에 좀 더 꼼꼼히 봤어야 했던 부분인데 불편함을 드리게 되어 죄송하다는 말씀 먼저 드립니다.

시작점, 끝점, 그리고 모든 방해물 간의 경우의 수를 행렬에 저장하고 이를 이용하여 푸는 풀이가 통과되는 것을 확인했습니다.

만들어지는 행렬을 상삼각행렬의 꼴을 가지도록 만들 수 있는데, 이러한 경우 O(k^3) 방식으로 풀리는 게 최적화를 통해 통과가 되고 있습니다.

그물 모양으로 방해물이 있는 경우, 대각선 모양으로 방해물을 두는 경우, 각 행과 열에는 하나의 방해물이 있는 경우등 여러가지 경우들을 추가하여 스트레스를 돌렸는데 뚫리는 코드가 시간초과가 나는 데이터를 발견하지 못했습니다.

원래 제 의도는 포함배제를 이용하는 것이였는데 지금 상황은 포함배제를 쓰지 않고도 풀릴 수 있습니다.

그래서, 이렇게 메모리 제한을 줄여서 O(k^2)의 공간복잡도를 가지는 방법들은 풀리지 않도록 메모리 제한 요청을 드립니다.



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