[c++] 백준 2529, 부등호

백준 2529

🌲 문제 요약

제시된 부등호 관계를 만족하는 k + 1 자리의 최대, 최소 정수를 각각 구하는 문제.

🌲 문제 풀이

함수 go를 재귀적으로 호출하여 문제를 해결한다.
go 함수 내에서는 0부터 10까지의 정수를 확인하여, 만약 idx == 0 또는 good(num[idx - 1], i + '0', a[idx - 1])을 만족하는 경우라면, idx + 1, num + to_string(i)를 인자로 하는 go 함수를 재귀적으로 호출한다.
idx == k + 1을 만족할 때 벡터 ret에 num을 push_back하고 return한다.

🌲 주의

go 함수를 재귀적으로 호출하는 과정에서, check[i]에 1을 저장한 다음, 호출 이후 다시 0을 저장해야 함을 잊지 않는다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int k, check[10];
char a[10];
vector<string> ret;

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

void go(int idx, string num) {
	if (idx == k + 1) {
		ret.push_back(num);
		return;
	}
	for (int i = 0; i < 10; i++) {
		if (check[i]) continue;
		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 >> k;
	for (int i = 0; i < k; i++) {
		cin >> a[i];
	}
	go(0, "");
	sort(ret.begin(), ret.end());
	cout << ret[ret.size() - 1] << '\n' << ret[0] << '\n';
	
	return 0;
}