qktlf789456   2년 전

벽부수기 문제랑 비슷하다고 생각하였습니다.

A위치에서 B위치까지 빙하를 벽이라고 가정하고, 벽을 부수며 갔을대

최소벽을 부숴도 되는 DP테이블(min_break_mat) 를 정의해서 저장해나가며 구했습니다.

A에서 시작하여 B위치에서 벽을 부순개수가 r일경우

(r+1)/2 를 정답으로 출력해줬습니다.

논리적으로 틀렸다면 이해가가지만, 시간초과는 잘 모르겠습니다. 입력단계에서 백조위치를 저장하는 최악의 경우 1500*1500 의 시간복잡도와

최악의경우 1500*1500 번의 BFS 뿐인데 시간초과이유를 알고싶습니다 ㅠ

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