알고리즘 :: 백준 :: Bruteforce :: 2529 :: 부등호

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다

문제접근

• k개의 부등호가 있다면, 숫자를 넣을 수 있는 공간은 k+1개이다. i번째 공간에 숫자를 넣었다면 i+1번째 공간에는 부등호를 만족하는 숫자들 중 하나를 고정하고 재귀를 계속 돌린 뒤 나오는 숫자를 저장하면 된다. 그리고 고정한 숫자를 해제하고 다른 경우를 찾으면 되는 전형적인 bruteforce 문제다.
• 최대 넣을 수 있는 공간은 10개, 부등호가 > > > > ... > >로 9개인 경우에 상한은 $10 \times 9 \times 8 ... \times 1$ 약 300만이므로 충분히 bruteforce로 풀 수 있다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

static int k;
static bool isUsed[10];
static char inequality[9];
static vector<string> ans;

inline bool isGood(char lhs, char rhs, char op) {
	if (op == '<') return lhs < rhs;
	else return lhs > rhs;
}

void solve(int idx, string str) {
	if (idx == k + 1) {		// K+1개 숫자 조합 만들어졌다면,
		ans.push_back(str);	// ans 벡터에 넣는다.
		return;
	}
	for (int i = 0; i < 10; ++i) {
		if (isUsed[i]) continue;	// 이미 숫자를 사용했다면 다음 숫자를 시도한다.
		// 첫 번째 인덱스이거나, 해당 자리에 넣을 수 있는 숫자인지 유효성을 판단한다. (백트래킹)
		if (idx == 0 || isGood(str[idx - 1], i + '0', inequality[idx - 1])) {
			isUsed[i] = true;		// 고정
			solve(idx + 1, str + to_string(i));	// 고정한 경우에 대해 계속 탐색
			isUsed[i] = false;		// 해제
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> k;
	for (int i = 0; i < k; ++i) cin >> inequality[i];
	
	solve(0, "");
	auto answer = minmax_element(begin(ans), end(ans));
	cout << *answer.second << '\n' << *answer.first << '\n';
}

결과