글 읽기 - 시간초과가 납니다

shie44167 7년 전 0

dfs로 풀고 있었는데 같은 부분집합을 체크하는데에서 중복이 발생해서 중복을 막으려고 체크 되어있는 수들의 순서값을 문자열로 만들어서 벡터에다 집어넣고 중복인지 아닌지 체크하게 했습니다만 for문과 재귀때문인지 시간초과가 나는데 다른 방법을 조언해주시면 감사하겠습니다.

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

int arr[21];
bool check[21];
vector<string> v;
int cnt = 0;

void dfs(int num, int n, int s) {
	if (num == s) {
		string str = "";
		int ch = 0;

		for (int i = 0; i < n; i++) {
			if (check[i] == true)
				str += i + '0';
		}

		for (int i = 0; i < v.size(); i++) {
			if (v[i] == str) {
				ch = 1;
				break;
			}
		}

		if (ch == 0) {
			cnt++;
			v.push_back(str);
		}
	}
	for (int i = 0; i < n; i++) {
		if (check[i] == true)
			continue;

		check[i] = true;

		dfs(num + arr[i], n, s);
		check[i] = false;
	}
}

int main() {
	int n, s; scanf("%d%d", &n, &s);

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	for (int i = 0; i < n; i++) {
		check[i] = true;
		dfs(arr[i], n, s);
		check[i] = false;
	}

	printf("%d\n", cnt);
}

flflds0811 7년 전 1

N이 최대 20까지밖에 안되므로

단순히 어떤수를 선택하고 안하고로 모든 경우를 나타내어도

O(2^20)밖에 안됩니다.

간단히 완전탐색으로 풀어보세요.

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

문제

문제

출처

ICPC

시간초과가 납니다

shie44167 7년 전 0

flflds0811 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말