인프런 커뮤니티 질문&답변
작성한 질문수
3-K 시간초과 나는 이유
작성
·
127
0
해당 코드가 시간초과가 나는 이유가 궁금합니다.
https://www.acmicpc.net/source/74630828
저의 대략적인 시간 복잡도는
1500 x 1500 x n
4^n <= r*c를 만족하는 자연수중 최대로 생각하여
1억이 넘지 않는다 판단하였습니다.
답변 1
0
큰돌
지식공유자
안녕하세요 ㅎㅎ
while (true)
{
for (int i = 0; i < 1505; i++)
{
fill(vis[i], vis[i] + 1505, 0);
fill(vis_water[i], vis_water[i] + 1505, 0);
}
dfs(st_y, st_x);지금 보시면 계속해서 초기화 -> dfs를 하고 있는데요.
이경우의 이 코드의 최대 시간복잡도는
1500 x 1500 x n 가 됩니다.
>> 저 n 은 아마 최댓값은 750이 될 것 같습니다.최악의 경우는요. (맨끝에 위치해있다 생각. 750번을 해야 만남)
그 경우에는
1,687,500,000가 됩니다. 즉, 16억짜리 코드가 됩니다. -> 시간초과가 나기 충분합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.