백준 1469: 숌 사이 수열

시험삼아 적당히 난이도 있는 문제를 풀어보자

https://www.acmicpc.net/problem/1469

 

일단 알고리즘 파악부터 하자. X의 크기가 최대 8이다. 이런 경우는 대게 브루트포스 내지 백트래킹 문제이다. 그러므로 나는 백트래킹으로 풀기를 결정했다.

 

이제 알고리즘을 결정했으니 문제를 풀자, input을 제외한 필요한 변수엔 무엇이 있을까?

우선 정답을 저장할 공간이 필요하다. 백트래킹을 위해 뒤에 원소를 넣고 빼는 것이 가능하고, 정답을 읽기위한 순회가 가능한 자료구조가 적당하다. 그래서 나는 배열이 적합하다고 판단했다. 여기서는 C++의 vector를 사용하기로 하였다. 백트래킹을 위한 함수에 매개변수로 전달하는 것보단 전역변수로 빼는 것이 시간을 덜 소모할것이다.

 

또 뭐가 있을까? 이전에 정답을 저장한 원소인지 파악하는 변수가 필요하다.

여기에다가 이전에 저장을 했다면 언제 저장을 했는지까지 파악하면 좋을 것이다.

그래서 나는 원소가 저장되는 위치를 기록하는 변수를 정의했다. 이 변수는 처음엔 전부 -1로 초기화되어있다. 그리고 원소를 저장할 때, 위치를 기록한다. 위치는 0 이상의 양수이기에 음수가 될 수 없어서, -1이면 저장된 적이 없다는 것을 나타내고, 0 이상의 수는 저장된 위치를 나타낸다.

 

여기서 이 변수를 단순 배열을 사용했는데, 이것이 가능했던 것은 집합 X가 다른 숫자로 구성이 되어있다는 점과, X의 원소가 0이상 16이하란 작은 값의 범위를 갖기 때문이다. 만약, 다른 숫자로의 구성이 아니라면 인덱스를 저장할 것이고, 원소의 범위가 천만 이상이라면 Map이나, 값 압축을 활용할 것이다. 하지만 단순하게 특정 값의 위치를 저장하는 것이 효과적이라 판단하였다.

 

이 다음 재귀 함수 내에서는 집합 X를 순회한다. 여기서 두 갈래로 나눈다. 이 값이 저장된적이 있느냐? 아니냐? 다.

만약 저장된 적이 없다면 일단 넣어보고 기록을 하자. 정답 배열의 사이즈면 위치를 기록하기 충분하다.

저장된 적이 있다? 그러면 이미 저장된 위치와 원소의 값을 합치고, 내가 넣을 원소의 위치와 동일한지 비교하자. 동일하면 넣고, 아니면 넘어가자.

 

마지막으로 숌 사이 수열을 출력하자 이 재귀함수가 정상적으로 작동된다면 정답 배열이 2 * N 만큼의 사이즈를 가질 것이다. 이 때, 정답을 출력하고 빠지면 된다. 시간을 더 빠르게 하기 위해, 그리고 정답이 여러개일 경우에도 하나만 출력을 위해, 마지막으로 정답이 없는 경우를 체크해야하기 위해, 출력했는지 여부를 판단하기 위한 전역 변수 Boolean도 추가하자. 

일단 출력하면 이 Boolean 값을 true로 설정, 재귀함수를 바로 빠져나와서 하나만 출력함을 보장한다. 만약 재귀함수를 마친 뒤에도 이 Boolean이 false라면 숌 사이 배열이 없다는 것을 나타내서, 그냥 -1만 출력하자.

 

사실 나는 여기까지 하고 바로 코드를 제출했다. 안타깝게도 "틀렸습니다"를 받았다. 이유를 보니 내가 문제를 다 안 읽었다는 사실을 깨달았다. 출력 문단에 만약 여러 개일 경우 사전 순으로 빠른 것을 출력하라고 되어있다.

즉, 입력 받은 수열을 정렬해서 사전 순으로 가장 빠른 것을 출력하도록 수정해야했다. 그렇게 해서 최종적인 코드는 다음과 같다.

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

int N, X[10], P[20]; // 각각 집합 사이즈, 집합 원소 그리고 저장 위치
vector<int> ans; // 정답을 저장할 공간
bool f = false; // 출력 여부

void solve()
{
	if (f) return; // 출력 된적이 있다면 재귀를 빠져나옴
	if (ans.size() == 2 * N) // 숌 사이 수열 완성시에는 출력
	{
		f = true; // 출력 여부 true
		for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; // 출력
		cout << '\n';
		return; // 빠져나가자
	}
	for (int i = 0; i < N; i++)
	{
		if (P[X[i]] == -1) // 저장된 적 없다?
		{
			P[X[i]] = ans.size(); // 저장 위치 기록
			ans.push_back(X[i]); // 정답 배열에 저장
			solve(); // 재귀
			ans.pop_back(); // 빼자
			P[X[i]] = -1; // 기록도 원위치
		}
		else if (P[X[i]] + X[i] + 1 == (int)ans.size()) // 저장된 적이 있고, 현재 저장할 위치와 동일하다?
		{
			ans.push_back(X[i]); // 저장!
			solve(); // 재귀
			ans.pop_back(); // 빼자
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(P, -1, sizeof(P)); // 위치를 -1로 초기화
	cin >> N; // 사이즈 입력
	for (int i = 0; i < N; i++) cin >> X[i]; // 원소 입력
    	sort(X, X + N); // 정렬
	solve(); // 재귀 실행
	if (!f) cout << -1 << '\n'; // 출력 된적 없으면 -1
}

이렇게 코드를 구성할 수 있다.

 

맞았습니다를 받았다.

20ms란 약간 느린 결과가 나왔으나, 그래도 맞았으니 넘어가자.