his130   2년 전

이 문제의 경우 그냥 DP 없이 풀어도 되겠다 하고 풀어봤는데 시간 초과가 나오네요.

근데 이동할 때마다 이동할 수 있는 map 이 줄어드니까 시간안에 들어올 수 있는거 아닌가요?..

어떤 식으로 대충 O(N) 값을 구할 수 있나요?? 

jh05013   2년 전

가능한 모든 경로를 따지는 코드입니다. 경로가 몇 개나 될까요?

his130   2년 전

아 그렇군요.. 

예를 들면 제 코드에서 한번 이동에 최대 3번의 호출을 불러 일으키니..

최대 1000 x 1000 칸에서는 3^1000000 이라는 호출이 생길 수 있는건가요?


이런식으로 계산하는게 맞나요..?

djm03178   2년 전

그 정도는 아니겠지만 (항상 3군데를 움직일 수 있는 것도 아니고, 경로 하나당 많아야 n+m 정도밖에 못 움직이므로), 감당할 수 없는 수준의 호출 횟수가 나오는 건 확실합니다.

his130   2년 전

감사합니다!

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