글 읽기 - 1095 시간초과...

wjsqjawns 8년 전 0

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

함수는 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까지 둘러봐야 하므로 엄청난 시간이 소모됩니다.

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

도와주세요 ㅠㅜ

#include<stdio.h>
#include<vector>
#include<stack>
#include<string.h>
using namespace std;
int a[100001], c[100001];
vector<int> v;
stack<int> st;
long long solve(int n, int i){
	long long j=1, cnt=0;
	while(1){
		if(n/((long long)v[i]*j)) cnt+=n/((long long)v[i]*j);
		else break;
		j*=v[i];
	}
	return cnt;
}
void nprime(int n){
	int i=2, j, cnt;
	st.push(1);
	for(; n!=1; i++)
		if(!(n%i)){
			st.push(i);
			while(!(n%i)) c[i]++, n/=i;
		}
}
void prime(int n){
	int i=2, j;
	a[1]=1;
	for(; i<=n; i++){
		j=2;
		while(i*j<=n)
			a[i*j]=1, j++;
	}
	for(i=2; i<=n; i++)
		if(!a[i])
			v.push_back(i);
}
int main(){
	int i, s, k, m, ans=1, cnt;
	scanf("%d%d%d",&s,&k,&m);
	prime(m);
	memset(a, 0, sizeof(a));
	a[1]=1;
	for(i=0; i<v.size(); i++)
		a[v[i]]+=solve(s+k,i)-solve(s,i)-solve(k,i);
	for(i=m; i>1; i--){
		memset(c, 0, sizeof(c));
		while(!st.empty()) st.pop();
		nprime(i);
		cnt=0;
		while(!st.empty())
			if(c[st.top()]>a[st.top()]){
				cnt=1;
				break;
			}
			else
				st.pop();
		if(!cnt){
			printf("%d",i);
			return 0;
		}
	}
	printf("-1");
}

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

문제

문제

출처

ICPC

1095 시간초과...

wjsqjawns 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말