5-L 14889번 - 스타트와 링크 시간복잡도 계산을 어떻게 해야 할지 모르겠습니다.

Question

안녕하세요 선생님. 문제를 풀다 이런 비트마스킹을 이용한 조합 문제에서 1억이 넘는지 확인을 어떻게 해야 할지 궁금해서 질문 남깁니다. 제 생각으로는 비트를 20개를 사용하니 2^20 - 1 만큼 연산을 하지만 비트가 N /2 만큼 켜진 것이 아니면 다음 연산으로 넘어가니 20C10 으로 보는것이 맞는건가? 라고 추측을 하는데 혹시 이게 맞을까요? 만약 이게 맞다면 20!이나 되는 큰 숫자를 시험도중에 대략적인 계산을 해보기에는 너무 크다는 생각이 드는데 TLE가 날지 어떻게 계산을 해봐야 할지 막막한데 방법이 있을까요?

큰돌 · Answer

안녕하세요 aass님 ㅎㅎ 제 생각으로는 비트를 20개를 사용하니 2^20 - 1 만큼 연산을 하지만 비트가 N /2 만큼 켜진 것이 아니면 다음 연산으로 넘어가니 20C10 으로 보는것이 맞는건가? 라고 추측을 하는데 혹시 이게 맞을까요? >> 2 ^ 20이 맞습니다. 20C10으로 해도 되구요. 정확히는 이 문제의 시간복잡도는 2 ^ 20 * 20이라고 보면 됩니다. (해당 정점 확인하는 dfs 로직이 있으니) 만약 이게 맞다면 20!이나 되는 큰 숫자를 시험도중에 대략적인 계산을 해보기에는 너무 크다는 생각이 드는데 TLE가 날지 어떻게 계산을 해봐야 할지 막막한데 방법이 있을까요? >> 엥 갑자기 20!이 나와버렸는데 2 ^ 20은 100만밖에 안되요. 20!는.. .훠어얼씬 큰수구요.(참고로 20!은 2432902008176640000 입니다.) 100만정도는 충분히 가능합니다. 그리고 aass님이 생각하신 1억정도면 충분히 아 이거 시간초과가 나겠구나 라고 생각하는것도 좋습니다. 감사합니다.