[C/C++] 백준 - 10597번 : 순열 장난

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

10597번: 순열장난

문제

kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다.

그런데 sujin이 그 파일의 모든 공백을 지워버렸다!

kriii가 순열을 복구하도록 도와주자.

 

입력

첫 줄에 공백이 사라진 kriii의 수열이 주어진다.

kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.

 

 

 

놓쳤던 부분 : 주어지는 순열은 최소 1개 최대 50개의 수로 이루어져있고 1부터 N까지의 수로 이루어져있다.

 

위 문장을 놓쳐 시간을 많이 허비한 문제이다. 위 문장만 제대로 확인하고 이해한 후 문제를 풀면 빠른 시간 내에 해결할 수 있었을텐데.

 

순열은 최대 50개의 수로 이루어져있고 1부터 N까지의 수로 구성되어있기 때문에 처음 입력으로 주어지는 수열의 길이를 이용하여 N이 어떤 수인지 알 수 있다.

 

예를 들어 입력으로 주어지는 문자열이 str이라고 했을 때, str의 길이가 9이하라고 하면 str의 길이 자체가 N이 될 것이다. 그래야 1~N을 이어붙인 순서가 바뀐 수열이기 때문일 것이다.

 

그럼 9보다 큰 길이를 가진 수열로 입력이 주어지면 어떻게 될까? 그럼 9까지는 동일하고 10부터는 하나의 수가 두 자리의 문자열을 이루게 된다. ex) "12" -> 2자리

 

그렇기에 총 문자열의 길이에서 9를 빼고 2로 나눈 값이 9보다 큰 값 두 자리수가 존재한다는 의미이다.

ex) 문자열의 길이를 15라고 하게 되면

     1) 9까지 존재한다는 가정은 참이 된다. 그렇기에 15-9=(총 6)의 길이를 가지는 각 두 자리의 문자열이 추가로 존재

     2) 10부터는 두 자리수이기 때문에 남은 문자열을 2로 나눈 3이 추가로 존재하는 값, 따라서 9+(6/2) = 12 (=N)

 

*** 처음에 놓쳤던 부분을 통해 위 N값만 확인할 수 있다면 이 문제는 백트래킹으로 쉽게 해결할 수 있다.

             

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>

using namespace std;

string str;
int sizeOfstr;
bool visited[51];

void input() {
	cin >> str;
	if (str.size() <= 9) sizeOfstr = str.size();
	else {
		sizeOfstr = 9 + ((str.size() - 9)/2);
	}
}

bool isValid(int x) {
	return (1 <= x && x <= sizeOfstr);
}

void func(int idx, string s) {
	if (idx == str.size()) {
		cout << s << endl;
		exit(0);
	}

	s += " ";
	string temp = "";
	for (int i = idx; i < str.size(); i++) {
		temp += str[i];
		if (!isValid(stoi(temp))) return;
		if (!visited[stoi(temp)]) {
			visited[stoi(temp)] = true;

			func(i + 1, s+temp);


			visited[stoi(temp)] = false;
		}
	}
}

void solution() {
	string Temp = "";
	for (int i = 0; i < str.size(); i++) {
		Temp += str[i];
		if (isValid(stoi(Temp)) && !visited[stoi(Temp)]) {
			visited[stoi(Temp)] = true;

			func(i + 1, Temp);

			visited[stoi(Temp)] = false;
		}
	}
}

int main() {
	fastio;
	input();
	solution();

	return 0;
}