olbbemi   2년 전

정답유출 방지를 위해서 핵심코드는 다 제거했고 의문점이 드는 곳만 남겨두었습니다.

이 문제를 저는 순열을 이용하여 완전탐색을 실행했는데 N개 중에 절반은 0으로 절반은 1로 초기화한 뒤 이를 next_permutation 으로 돌렸습니다.

주어진 수의 범위가 1 ~ 100이라면 시간조과가 발생하는게 맞지 않나 싶습니다만 아무런 문제 없이 답이 나와서 질문드려봅니다.

ho94949   2년 전

그래서 계산한 시간복잡도가 어떻게 되나요?

olbbemi   2년 전

N! 아닌가요?

chogahui05   2년 전

20C10 * 400 정도 될 건데요. 최악의 경우에 20개중 10개는 1을 놓아야 하니까요.

20C10 = 184756이네요. naive하게 돌리면 x400



시간 초과 안 날 거 같은데요.

olbbemi   2년 전

아.. 잘못봣네요 ㅎㅎ N 이 20이엿구나. N 의 범위가 100이라는줄알앗네요.

감사합니다.

orslow   2년 전

절반은 0, 절반은 1로 해서 next_permutation 돌린다는 방법이 감탄스럽네요. 덕분에 한수 배우고 갑니다 고맙습니다.

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