백준 2529 부등호 // 재귀로 완탐구현 , string 정렬시주의

2529번: 부등호 (acmicpc.net)

 

* 재귀로 완탐구현 

기본꼴 : go(index, 임시저장결과값)

1. 종료조건

2. 직접해보면서 일반화하라.

마지막숫자 == num[idx-1]

비교할숫자 == i

비교할op == a[idx-1] 임을 알 수 있다.

 

* string 정렬시주의

"23"

"123" 비교시

앞부터 하나씩 비교 하므로, 23이 더 크게됨에 주의.

#include<bits/stdc++.h>
using namespace std;
int n, temp, check[14];
vector<string> ret;
char a[14];

bool good(char a, char b, char op) {
	if (op == '<' && a < b) return true;
	if (op == '>' && a > b) return true;

	return false;

}

void go(int idx, string num) {
	if (idx == n+1) {
		ret.push_back(num);
		return;
	}
	for (int i = 0; i <= 9; ++i)
	{
		if (check[i]) continue;
		//최초 or good(저장된마지막숫자,new숫자,op)
		//매개변수 => 저장용, 확인용 으로 사용하라.
		if (idx == 0 || good(num[idx-1],i+'0', a[idx-1])) {
			check[i] = 1;
			go(idx + 1, num + to_string(i));
			check[i] = 0;	//원복
		}
	}
	return;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];	//등호 저장
	}
	go(0, "");
	sort(ret.begin(), ret.end());
	
	cout << ret[ret.size()-1] << "\n";
	cout << ret[0] << "\n";
	return 0;
}