[구름 알고리즘 먼데이 챌린지] Week5 : 3. 수 이어 붙이기

완탐문제라고 생각했고 재귀호출과 백트래킹을 적절히 사용하여 가능한 경우를 모두 구해주어 최소 값을 갱신해 주도록 하였다. 한 가지 함정에 주의하자! 문제에서 겹쳐서 이어 붙일 수 있는 경우에도 그냥 이어 붙있 수 있다고 하지만 조금만 생각해 보면 최소 값을 위해서는 가능한 경우 항상 겹쳐서 이어 붙이는 것이 합리적이라는 것을 알 수 있다. 

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n;
long long ans = 9999999999999999, num;
vector<int> numbers(9, 0), visited(9, 0);

void dfs(int cnt, string number) {
	if (cnt == n) {
		num = stoll(number);
		if (ans > num) ans = num;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (visited[i]) continue;
		int last = number.back() - '0';
		visited[i] = 1;
		if (last == numbers[i] / 10) dfs(cnt + 1, number+ to_string(numbers[i] % 10));
		else dfs(cnt + 1, number + to_string(numbers[i]));
		visited[i] = 0;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	
	for (int i = 0; i < n; i++) cin >> numbers[i];

	for (int i = 0; i < n; i++) {
		visited[i] = 1;
		dfs(1, to_string(numbers[i]));
		visited[i] = 0;
	}

	cout << ans;
}

Line 21, 22 부분이 겹쳐서 이어 붙일 수 있는 경우에 대한 분기조건이다.

visited은 같은 숫자를 중복하여 사용하는 것을 막기 위해 사용했고 재귀 호출 종료 조건에 도달했다 돌아오는 경우 visited를 0으로 초기화 해주는 백트리킹을 적용하여 가능한 모든 경우를 구할 수 있도록 해주었다.

 

해설

해설 풀이에서는 STL의 next_permutation() 함수를 사용하여 좀 더 간단한 풀이 방법을 소개하고 있다.

#include <iostream>
#include <string>
#include <algorithm>
typedef long long ll;
using namespace std;

int n;
const int MAX = 8;
string S[MAX];

ll Solve() {
	string ret = S[0];
	for (int i = 1; i < n; ++i) {
		if (ret.back() == S[i][0]) ret.push_back(S[i][1]);
		else {
			ret.push_back(S[i][0]);
			ret.push_back(S[i][1]);
		}
	}
	return stoll(ret);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll ans = 1e18;
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> S[i];

	// C++의 next_permutation은 항상 사전순으로 바로 다음에 오는 순열을 만들기 때문에,
	// 모든 순열을 탐색하기 위해서는 반드시 처음에 배열을 정렬해주는 과정이 필요합니다!
	sort(S, S + n);
	do {
		ans = min(ans, Solve());
	} while (next_permutation(S, S + n));
	cout << ans;
	return 0;
}

next_permutation()함수를 사용하여 가능한 모든 경우의 순서를 참조하고 현재까지 만들어진 숫자 ret의 끝 자리와 이어 붙일 수들의 앞 자리를 비교하며 겹쳐서 이어 붙일 수 있는 경우와 그렇지 않은 경우를 if 조건문을 통해 구분해 주고 있다.

순열 기법을 사용한 다는 것보다는 문자열에서 push_back을 해줄 경우 += 과 같은 효과를 기대할 수 있다는 점에 놀라며 또 한가지 배울 수 있었다.