durano   4년 전

백트래킹으로 어찌 해보려고 하는데, 계속 시간초과가 나네요.. 혹시 백트래킹으로는 풀 수 없는 문제입니까??

djm03178   4년 전

저는 오히려 비트마스킹으로 푼 사람을 본 적이 없습니다. 백트래킹으로도 충분히 가능합니다. 다만 백트래킹을 어떻게 하느냐에 달렸을 뿐입니다.

1. k보다 적게 가르치는 게 k개를 가르치는 것보다 이득일 리가 없으니, v.size() == k일 때만 검사해도 충분합니다.

2. 사실 v에 넣는 것 자체가 비효율적입니다. c라는 문자가 등장했는지를 x[c]에 1 또는 0으로 표시해놓으면 각 글자를 뽑았는지 여부를 한 번에 알 수 있는데, v에 넣었기 때문에 k개씩이나 검사해야 하기 때문입니다.

baekjoon   4년 전

제가 온라인 강의에서 비트마스킹으로 풀어서 그런 것 같습니다. 

durano   4년 전

감사합니다! 결국 문제는 백트래킹 작동 방식에 있었네요.. 비트마스킹은 백트래킹을 좀 더 간편하게 할 수 있는 도구였구요.

말씀해주신 부분 참고하여 수정해서 AC받았고 비트마스킹으로도 해결했습니다!

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