백준 10448

백준 10448 : 유레카 이론

1. 1~k 사이의 숫자에서 조합으로 3개 뽑고
2. 3 숫자의 삼각수를 더해서
3. k와 같으면 1, 아니면 0 출력

이렇게 했더니 시간 초과가 뜸. 왜 틀렸을까?

코드

#include <iostream>
#include <vector>

using namespace std;

int t, k;
vector<int> v;
int ans, ret;

int sumTri(vector<int> v) {
	ret=0;
	for(int i=0; i<v.size(); i++) {
		ret+=v[i]*(v[i]+1)/2;
	}
	
	return ret;
}

void combi(int start, vector<int> v, int k) {
	if(v.size()==3) { //3개 고른 경우 
		if(sumTri(v)==k) {
			ans=1;
			return;
		}
		
		return;		
	}
	
	for(int i=start+1; i<k; i++) {
		if(ret==k) {
			return;
		}
		v.push_back(i);
		combi(i, v, k);
		v.pop_back();
	}
	
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>t;
	while(t--) {
		ret=0;
		ans=0;
		cin>>k;
		combi(0, v, k);
		
		cout<<ans<<'\n';	
	}	
	
	return 0;
}