park780172   5년 전

간단한 문제 같은데 계속 86%에서 시간 초과 나네요..

이게 아주 큰 범위의 숫자가 주어져서 시간 초과 나는건지

아니면 무한 반복 때문에 시간 초과가 나타는건지도 잘 모르겠습니다.

혹시나 후자때문에 발생한 것일까봐

특수한 모양의 예제까지 다 생각하여 넣어봤지만

시간 초과의 원인이 될만한 예제를 찾지 못 하겠네요.

혹시나 힌트나, 도움 주실 수 있는 분 계실까요?!

참고로 저는 밑에처럼 사용합니다!!

Map[행][열] = Map[y][x] = Map[i][j]

newdeal   5년 전

안녕하세요.

벡터로 이문제를 구현하셨는데, 89줄을 보시면 지금까지 지나온 좌표들을 검사하하는데,

이문제의 조건인 M과N은 500까지 이고, 만약 최악의 경우면 2만개가 넘는 좌표를 

(1), (1,2) ,(1,2,3)  ... (1,2,3, ... 20000) 처럼 검사를 한것인데,

이는 O((N*M)^2)을 소요해 시간 초과를 일으킨 것 같습니다..(잘못 계산한거라면 밑의댓글로 정정해주시면 감사하겠습니다.)

벡터보다는 노드 기반 컨테이너(map,set ... )로 구현해 서칭하는 시간을 줄이시면 이 시간문제를 해결하실것같습니다.

park780172   4년 전

@newdeal

댓글 감사합니다. 다른방법으로 해결하였지만..


여튼우선 set으로도 시간 초과 나옵니다. map으로 해봐야겠네요!

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