redball_var   2년 전

입력받은 문자열를 조합으로 뽑는 방식을 이용했습니다.

입력받은 문자 n개 중에 1개, 2개, ..., n개를 뽑았습니다.

그래서 만든 조합이 필랜드롬인지 체크했습니다.

그런데. 30C1 + 30C2 + 30C3 + ... + 30C30 이 10억이 좀 넘어서 시간초과가 납니다.

시간 줄이려고 필랜드롬이 아닌 경우는 가지치기를 해봤는데도 시간초과가 나네요..

어떻게 풀어야할지 감이 안오는데 힌트부탁드립니다.ㅠㅠ

kkw564   2년 전

일단 접근자체가 아에 잘못된 것 같습니다.


30개의 문자열이면 최소 부분문자열이 ( 2^n )- 1개(공집합제외)인데 10억이면 10초입니다.


다른 알고리즘을 생각해보셔야 할 것같네요 구글링을 통해서 알고리즘을 공부하시는 것도 좋은 방법중 하나라고 생각합니다.

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