글 읽기 - 시간초과 질문입니다

jhtop96 3년 전 0

저는 dfs로 문제를 해결하였습니다.

답은 나오지만 계속 시간초과가 뜨고 있는 상황입니다.

해당 문제를 풀이할때 dfs로 -10부터 10까지의 모든 수들의 조합을 확인하는 것이 문제인 것인가요?

dfs로 풀 수 없는 문제인지 궁금합니다!!

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int N;
vector<char> v;
vector<int> list;
bool visited[21];
int A[21];

void dfs(int n);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N * (N + 1) / 2; i++) {
		char a;
		cin >> a;
		v.push_back(a);
	}

	int temp = -10;
	for (int i = 0; i < 21; i++) {
		A[i] = temp;
		temp++;
	}

	dfs(0);
}

void dfs(int n) {
	if (n == N) {

		int s = 0;
		int check = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int num = 0;
				if (i <= j) {
					for (int k = i; k <= j; k++) {
						num += list[k];
					}
					if (v[s] == '-') {
						if (num < 0)
							check++;
					}
					else if (v[s] == '+') {
						if (num > 0)
							check++;
					}
					else {
						if (num == 0)
							check++;
					}
					s++;
				}
			}
		}

		if (check == N * (N + 1) / 2) {
			for (int i = 0; i < list.size(); i++)
				cout << list[i] << " ";
			exit(0);
		}
		return;
	}

	for (int i = 0; i < 21; i++) {
		if (!visited[i]) {
			visited[i] = true;
			list.push_back(A[i]);
			dfs(n + 1);
			visited[i] = false;
			list.pop_back();
		}
	}
}

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

문제

문제

출처

ICPC

시간초과 질문입니다

jhtop96 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말