47번째 줄을 제외를 안 시키면 어떻게 되냐고 물어보셨나요? 그건 아닌 거 같고요.
그리고 45번째 줄 보시면 왜 시간초과 나는지 바로 보이네요.
i = 1부터 20까지 쭉 돌잖아요. 이건 어떤 함축적인 의미를 포함하냐면요.
순서 상관 있다는 소리에요. 순서가 상관이 있다 = permutation이더라.
그러면 20명 중에서 10명을 뽑는데 순서 상관 있다. 그러면 20C10이 아니라 20P10이겠죠?
20P10 = 20*...*10 >> 10! * 2^10 이므로 시간 초과 납니다. N=4 정도로 작은 테케 만들어 보시고 돌려 보세요.
baek_su 5년 전
제일 아래부분 dfs 들어가는 for문에서 for(int i = 1 ; i<N ; i++) 이런식으로 앞에 골랐던 수들을 제외를 안시켜주면
시간복잡도 계산이 어떻게 되나요?
시간복잡도가 생각이 잘 안나네요...
대충 20C10 *100 정도로 생각했는데
앞부분을 제외 안시키니까 시간 초과가 뜨네요...