글 읽기 - [1469]숌 사이 수열 질문(고통스럽습니다..ㅠ)

gumdung 3년 전 0

그냥 순열로 확인해준 후 답을 도출 하려했더니 20! 이라 당연스럽게 시간초과가 발생하더라구요.

그래서 곰곰이 생각해보았는데

1~n까지 돌면서 그 수만큼 점프해서 점프한 자리에 수가 없으면 채워넣고 이미 다른 수가 있거나 배열의 범위를 벗어나면 되돌아가는 방식으로 짜보았는데,,,,,틀렸네요.

뭐가 어떻게 틀렸는지 안보여서 고통스럽습니다 ㅠㅠ

조금이나마 도움될 말씀해주시면 감사하겠습니당

#include<bits/stdc++.h>

using namespace std;

int n;
bool flag = false;
int ans[25],check[25];
vector<int> v;

void dfs(int total, int cnt, int pos, int x);

int main()
{
	cin >> n;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++) {
		memset(ans, -1, sizeof(ans));
		memset(check, 0, sizeof(ans));
		check[v[i]] = 1;
		dfs(0, 0, 0, v[i]);
		if (flag)break;
	}
	if (flag == false)cout << -1;
	return 0;
}
void dfs(int total,int cnt, int pos, int x)
{
	if (pos >= n * 2 || ans[pos] != -1) 
		return;
	if (total >= n * 2 - 1) {
		if (!flag) {
			ans[pos] = x;
			flag = true;
			for (int i = 0; i < n * 2; i++)
				cout << ans[i] << " ";
		}
		return;
	}
	if (cnt == 0) {
		ans[pos] = x;
		dfs(total + 1, cnt + 1, pos + x + 1, x);
		ans[pos] = -1;
	}
	else {
		ans[pos] = x;
		for (int i = 0; i < v.size(); i++) {
			if (!check[v[i]]) {
				check[v[i]] = 1;
				x = v[i];
				for (int j = 0; j < n * 2; j++)
					if (ans[j] == -1) {
						dfs(total + 1, 0, j, x);
					}
				check[v[i]] = 0;
			}
		}
		ans[pos] = -1;
	}
}

gumdung 3년 전 0

이코드 버렸습니다

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

문제

문제

출처

ICPC

[1469]숌 사이 수열 질문(고통스럽습니다..ㅠ)

gumdung 3년 전 0

gumdung 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말