baek_su   2달 전

제일 아래부분 dfs 들어가는 for문에서 for(int i = 1 ; i<N ; i++) 이런식으로 앞에 골랐던 수들을 제외를 안시켜주면

시간복잡도 계산이 어떻게 되나요?


시간복잡도가 생각이 잘 안나네요...

대충  20C10 *100 정도로 생각했는데

앞부분을 제외 안시키니까 시간 초과가 뜨네요...

chogahui05   2달 전

47번째 줄을 제외를 안 시키면 어떻게 되냐고 물어보셨나요? 그건 아닌 거 같고요.

그리고 45번째 줄 보시면 왜 시간초과 나는지 바로 보이네요.

i = 1부터 20까지 쭉 돌잖아요. 이건 어떤 함축적인 의미를 포함하냐면요.

순서 상관 있다는 소리에요. 순서가 상관이 있다 = permutation이더라.

그러면 20명 중에서 10명을 뽑는데 순서 상관 있다. 그러면 20C10이 아니라 20P10이겠죠?

20P10 = 20*...*10 >> 10! * 2^10 이므로 시간 초과 납니다. N=4 정도로 작은 테케 만들어 보시고 돌려 보세요.

baek_su   2달 전

답변 감사합니다~!

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