4-F 질문입니다

Question

안녕하세요, 큰돌님 완전탐색을 해서 풀었습니다. 제가 생각한 시간초과의 이유가 맞는지 궁금합니다. 2^26으로 하면 시간복잡도는 대충 10^7? 10^8정도인데, cal연산의 시간복잡도는 어림잡아 50*15을 해서 10^3 정도여서 10^8 * 10^3 을 하면, 시간복잡도는 어림잡아 10^11 정도가 되어 시간초과가 나는건가요? https://www.acmicpc.net/source/61970109

gdgd · Answer

이해됐습니다 답변감사합니다!

kundol · Answer

안녕하세요 동훈님 ㅎㅎ void go(int depth,int st){ if (depth > K){ ret = max(ret,cal()); return; } for (int i = st; i < 26; i++){ if (check[i]) continue; check[i] = true; go(depth+1, i+1); check[i] = false; } } 이코드는 2^26이 아니라 26!코드입니다. 매번 26, 25.. 이렇게 함수를 호출하고 있습니다. int cal(){ int cnt = 0; for (int i = 1; i <= N; i++){ bool doit = true; for (char c : A[i]){ if (!check[c-97]){ doit = false; break; } } if (doit) cnt++; } return cnt; } cal 같은 경우 기저사례에 있고 한번밖에 사용되지 않기 때문에 그닥 시간에 미치는 영향은 없습니다. 즉, 26!이 동훈님의 코드의 시간복잡도입니다. 26!은 403291461126605635584000000이라서 시간초과가 나는 것 같습니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.