글 읽기 - 이 문제 재귀로는 풀 수 없나요?

rhkswls98 1년 전 0

조합 이라고 생각해서 재귀로 풀어보려고 했는데 답이 엉뚱하게 나와서 어디서 구현이 잘못된건지 잘 모르겠습니다..

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
int ret;
int x;
bool vst[1000001];
vector<int> v;

void func(int n, int sum){
	if(n == 2){
		if(sum == x) ret++;
		return;
	}
	for(int i=0; i<v.size(); i++){
		if(!vst[i]){
			vst[i] = 1;
			func(n+1, sum + v[i]);
			vst[i] = 0;
		}
	}
	return;
}
int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	while(n--){
		int a;
		cin >> a;
		v.push_back(a);
	}
	
	cin >> x; //주어진 x
	
	sort(v.begin(), v.end());
	func(0,0);
	cout << ret;
	return 0;
}

kokosoko59 1년 전 0

첫번째 고르는 수가 두번째 고르는 수 보다 작다는 조건을 추가해주시면 답은 제대로 나올것 같습니다. 그런데 이 문제는 n이 커서 조합으로 풀기에는 시간초과가 날 것 같습니다.

rhkswls98 1년 전 0

아 감사합니다 !! 시간초과도 고려를 못했네요 많이 배워갑니다 선생님

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

문제

문제

출처

ICPC

이 문제 재귀로는 풀 수 없나요?

rhkswls98 1년 전 0

kokosoko59 1년 전 0

rhkswls98 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말