[ boj : 1469] 숌 사이 수열

www.acmicpc.net/problem/1469

1469번: 숌 사이 수열

문제 : 현재 위치한 수와 같은 수 사이에는 이 수 만큼 수들이 존재하도록 수열을 만들어라

 

해설 : ,,,,,,이 문제 드럽게 힘들게 풀었습니다.

먼저 이 문제를 통해 브루트포스 부분이 약하다는 걸 뼈저리게 느꼈습니다.(열심히 다시 문제를 쭉쭉 풀어나가야겠어요)

 

첫번째로 막연하게 생각해볼 수 있는 방법은 '순열'입니다. 예제 케이스로 보면 112233 의 6개의 숫자들을 332211까지 돌아보면서 해당되는 조건 1,2번을 다 만족시키면 출력하고 끝내면 되죠.

그러나 시간초과에 걸리고 말겁니다(필자가 그랬습니다) 이유는 n의 크기는 10 이니 수들의 최대 개수는 20이 됩니다.그러면 이를 순열로 풀려고 했으면 O(20!)의 시간복잡도를 가지게 됩니다. (10억을 훨씬 넘는 수죠)

 

다른 방법을 생각해 봐야합니다.(djm03178님 항상 감사드립니다)

바로 선택한 수 i 와 i + a[i] +1 을 동시에 확인하는 것입니다. 즉, 절대로 답을 만들 수 없는 경우의 수들을 커팅해 나아가는 것 이죠. 그러면 마지막에 도달했을때 만들어진 수열이 맞는지 안맞는지 확인할 필요도 없이 항상 올바른 수열만 만들어지게 되는 것 입니다.

 

1)i 와 i+a[i]+1 번째에 수를 넣을 수 있는지 확인합니다.

2)만약 넣을 수 있다면 수를 넣고 재귀함수로 들어간 후 다음 수를 선택하여 비교합니다.

이때 재귀함수로 들어갔는데 현재 위치에 수를 넣으려고 했는데 이미 다른 수가 존재한다면, 다음 자리로 넘어가서 확인해 줍니다.

3)depth 가 n*2 에 도달했을땐 조건에 맞는 수열이 사전순으로 가장 앞서있으므로 출력해주고 종료하면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;

int n;
bool flag = false;
int ans[25], visit[25];
vector<int> v;
void dfs(int depth);

int main()
{
	cin >> n;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	memset(ans, -1, sizeof(ans));
	dfs(0);
	cout << -1;
	return 0;
}
void dfs(int depth)
{
	if (depth == n*2) {
		for (int i = 0; i < n * 2; i++)
			cout << ans[i] << " ";
		exit(0);
	}
	if (ans[depth] != -1) {
		dfs(depth + 1);
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visit[i] && depth + v[i] + 1 < n * 2 && ans[depth] == -1 && ans[depth + v[i] + 1] == -1) {
			visit[i] = 1;
			ans[depth] = ans[depth + v[i] + 1] = v[i];
			dfs(depth + 1);
			ans[depth] = ans[depth + v[i] + 1] = -1;
			visit[i] = 0;
		}
	}
}