wjsqjawns   8달 전

시간초과가 나오는 경우가 많아서 질문 올립니다.


함수는 3가지이며, 각각 역할은 이렇습니다.

1. void prime(int n) : n보다 작거나 같은 소수들을 vector<int> v에 넣습니다.

2. nprime(int n) : n을 구성하는 소수를 stack<int> st에 넣고, 그 개수를 배열 c에 넣습니다.

3. long long solve(int n, int i) : n!을 구성하는 v[i]의 개수를 반환합니다.

그래서 결국 배열 a[v[i]]는 (s+f)C(s)를 구성하는 v[i]의 개수를 나타냅니다.


본론으로 돌아와서, 시간초과가 일어나는 부분은 47번째 줄부터입니다.

m이 클 경우, 스택 st 안의 수도 많아지며, i=m부터 i=2까지 둘러봐야 하므로 엄청난 시간이 소모됩니다.

고심을 해 봤는데도 어떻게 하면 쓸데없는 연산을 줄일 수 있을지 모르겠습니다.

도와주세요 ㅠㅜ

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