sam165   4년 전


시간초과나서 멈추네요..

어느 부분이 문제일까요..

도와주세요!

djm03178   4년 전

67번째 줄의 &를 &&로만 고치면 통과됩니다.

둘은 결과적으로는 비슷한 논리가 되지만, 실제로 실행되는 과정이 전혀 다릅니다. && 연산자는 short circuit evaluation이 되기 때문에 좌항을 먼저 평가하여 거짓으로 드러나면 우항을 아예 실행도 하지 않는 반면에, &는 그런 거 없이 무조건 양쪽을 다 실행하므로 &를 사용했을 경우 O(nm)개의 칸을 방문할 때마다 O(nm)개의 칸을 전부 검사해서 남은 토마토가 있는지를 세기 때문에 O((nm)^2)이 되는 바면, &&를 사용하면 마지막에 덱이 비게 되는 딱 한 순간에만 검사를 하게 되기 때문에 O(nm)이 됩니다.

sam165   4년 전

감사합니다!!! 

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