[2529] 부등호

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<set>
#include<cstdlib>
#include<sstream>
using namespace std;

char a[100];
int p[1001];
int n;

int checkarray[11];;
long  long real = 100000000;
vector <int> temp;
vector<vector<int>> all;
bool check() {
	bool flag = true;
	for (int i = 0; i < n; i++) {
		if (a[i] == '<') {
			if (temp[i] < temp[i + 1]) flag = true;
			else { flag = false; break; }
		}
		else {
			if (temp[i] > temp[i + 1]) flag = true;
			else { flag = false; break; }
		}
	}
	return flag;
}
void solve(int cnt) {
	if (cnt == n +1) {
		if (check()) {
			all.push_back(temp);
			/*for (int i = 0; i < temp.size(); i++) {
				cout << temp[i];
			}cout << '\n';*/
		}
		return;
	}
	for (int i = 0; i <= 9; i++) {
		if (checkarray[i] == 1) continue;
		checkarray[i] = 1;
		temp[cnt] = i;
		solve(cnt + 1);
		checkarray[i] = 0;
 	}

};
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	temp.resize(n + 1);
	solve(0);
	
	auto last = all[all.size() - 1];
	for (int i = 0; i < last.size(); i++) {
		cout << last[i];
	}cout << '\n';
	auto first = all[0];
	for (int i = 0; i < first.size(); i++) {
		cout << first[i];
	}
	return 0;
}

시간 초과 날 줄 알았는데 정답 되버렸다..

다시 고민해야 겠다...

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<set>
#include<cstdlib>
#include<sstream>
using namespace std;

char a[100];
int p[1001];
int n;

int checkarray[11];;
long  long real = 100000000;
vector <int> temp;
vector<vector<int>> all;
bool check() {
	bool flag = true;
	for (int i = 0; i < n; i++) {
		if (a[i] == '<') {
			if (temp[i] < temp[i + 1]) flag = true;
			else { flag = false; break; }
		}
		else {
			if (temp[i] > temp[i + 1]) flag = true;
			else { flag = false; break; }
		}
	}
	return flag;
}
void solve(int cnt) {
	if (cnt == n +1) {
		if (check()) {
			all.push_back(temp);
			/*for (int i = 0; i < temp.size(); i++) {
				cout << temp[i];
			}cout << '\n';*/
		}
		return;
	}
	for (int i = 0; i <= 9; i++) {
		if (checkarray[i] == 1) continue;
		if (cnt >= 1) {
			if (a[cnt - 1] == '<') {
				if (temp[cnt - 1] > i) { continue; }

			}
			else if(a[cnt-1]=='>'){
				if (temp[cnt - 1] < i) { continue; }
			}

		}
		checkarray[i] = 1;
		temp[cnt] = i;
		solve(cnt + 1);
		checkarray[i] = 0;
 	}

};
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	temp.resize(n + 1);
	solve(0);
	
	auto last = all[all.size() - 1];
	for (int i = 0; i < last.size(); i++) {
		cout << last[i];
	}cout << '\n';
	auto first = all[0];
	for (int i = 0; i < first.size(); i++) {
		cout << first[i];
	}
	return 0;
}

숫자를 조합할때 check 해주면 훨씬 빨라진다!!!

좋은 웹페이지 즐겨찾기