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

문제

문제링크
두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A => < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다.

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다.

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.

문제접근

• k의 범위가 9 까지고, 사용할 수 있는 숫자도 10개 뿐이다. 최악의 경우를 고려해도 $10! = 3,628,800$이므로 bruteforce로 충분히 풀만하다.
• 어렵게 생각한다면 한참동안 해맬 수 있는 문제다. Bruteforce를 적용할 수 있다면 우선 효율성을 생각하기 보다는 AC를 받는것을 목표로 한 뒤에 최적화를 하자.
• 숫자를 넣을 수 있는 k + 1개 공간에 0~9까지의 수를 선택해서 넣는 문제라고 이해한 뒤, 후보를 만들었다면 부등호가 올바르게 적용되는지 판단한다.
• 부등호가 올바르게 적용되는 후보를 찾았다면 이 숫자를 어딘가에 저장해둔 뒤 min, max를 구하면 된다.
• 아래 코드에서는 이 문제를 재귀를 이용한 bruteforce와 조합을 이용한 bruteforce 두 가지 방법으로 풀었다.

재귀 풀이

• 재귀 함수는 solve(idx, str)로 돼있다.
  • idx는 idx번째 공간을 의미한다.
  • str은 지금까지 만든 문자열을 의미한다.
• for문을 이용해서 0부터 9까지의 수 중 idx번째 공간에 들어갈 수 있는 적합한 숫자를 찾는다.
  • 적합한 숫자는 이전 숫자와 부등호 관계가 성립해야 한다.
• Bruteforce-재귀 방법 따라 어떠한 경우를 고정시켜준 뒤 다음 재귀를 수행하고 고정해준 내용은 해제 시켜준다.
• idx가 범위를 넘어갈 경우 지금까지 만들었던 str을 ans 배열에 넣는다.
• 여기서는 비효율적으로 ans 배열을 따로 만든 뒤 std::minmax() STL로 답을 구했지만, 재귀의 종료조건에서 바로 strcmp나 문자열 대소비교로 답을 구하는 것이 효과적이다.

조합 풀이

• 위에서 이 문제는 숫자를 넣을 수 있는 k + 1개 공간에 0~9까지의 수를 선택해서 넣는 문제라고 언급했다.
• 따라서 0~9까지의 수 중 k + 1개를 선택한 뒤 적합한 부등호 관계를 가지는지 판단하면 된다.
• a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 배열을 만든 뒤 std::next_permutation()을 사용한다.
• k + 1개 숫자를 tmp[] 배열에 넣은 뒤 부등호 관계가 성립함을 검사하고 strcmp()로 답을 찾는다.
• $O(10 \times 10!)$ 알고리즘이므로 굉장히 오래걸리지만 확실한 방법이다.

순열 풀이

• 부등호 조합은 들어갈 수 있는 숫자의 대소 정보를 포함한다.
• 예를 들어, < > < > 라는 입력이 있을 때,
  1번째 수 < 5번째 수 > 3번째 수 < 4번째 수 > 2번째 수 또는
  1번째 수 < 5번째 수 > 2번째 수 < 4번째 수 > 3번째 수 라는 정보를 포함한다.
• 따라서 우리는 k + 1개 숫자를 뽑을 필요가 없이, 그냥 k + 1개 숫자를 가지고 부등호 관계가 성립함을 보여도 상관없다.
• 말이 조금 햇갈릴 수 있다.
  즉, 0~9까지의 수 중 k + 1개를 뽑는 행위가 무의미하다는 것이다.
• 애초에 k + 1개 수를 가지고 있고, 그것들의 모든 순열에 대해 부등호 관계를 검사해도 된다는 의미다.
• 가장 작은 수를 찾기 위해서는 0, 1, ..., k 라는 k + 1개의 숫자들로부터 정방향으로 순열을 만들면 되고,
• 가장 큰 수를 찾기 위해서는 9, 8, ..., 9-k 라는 k + 1개의 숫자들로부터 역방향으로 순열을 만들면 된다.

코드

Bruteforce - 재귀

#include <iostream>
#include <cstring>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

int N;
bool used[10];
char op[9], minAns[10], maxAns[10];

inline bool isValid(char lhs, char rhs, char op) {
	if (op == '<') return (lhs < rhs) ? true : false;
	return (lhs > rhs) ? true : false;	
}

void show(char* n) {
	for (int i = 0; i <= N; ++i) cout << n[i];
	cout << '\n';
}

void solve(int idx, char* n) {
	if (idx == N + 1) {
		if (strcmp(minAns, n) > 0) memcpy(minAns, n, N + 1);
		if (strcmp(maxAns, n) < 0) memcpy(maxAns, n, N + 1);
		return;
	}
	for (int i = 0; i <= 9; ++i) {
		if (used[i]) continue;
		if (idx == 0 || isValid(n[idx - 1], i + '0', op[idx - 1])) {
			n[idx] = i + '0';
			used[i] = true;	
			solve(idx + 1, n);
			n[idx] = '0';
			used[i] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> op[i];
	fill(minAns, minAns + N, '9');	// Init 'minAns' to '999...' for proper strcmp().
	// fill(maxAns, maxAns + N, '0'); // 'maxAns' is already initialized cause it is a static variable.
	char num[10] = {'0', };
    	solve(0, num);
	show(maxAns);
	show(minAns);
}

Bruteforce - 조합

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    
    char op[n];
    for (int i = 0; i < n; ++i) cin >> op[i];
    
    char tmp[n + 1];
    char ansMax[n + 1], ansMin[n + 1];
    for (int i = 0; i <= n; ++i) ansMax[i] = '0', ansMin[i] = '9';
    do {
        for (int i = 0; i <= n; ++i) tmp[i] = a[i] + '0';
        bool valid = true;
        for (int i = 0; i < n; ++i) {
            if ((op[i] == '<' && tmp[i] > tmp[i + 1]) || 
            (op[i] == '>' && tmp[i] < tmp[i + 1])) { valid = false; break; }
        if (!valid) continue;
        if (strcmp(ansMax, tmp) < 0) strcpy(ansMax, tmp);
        if (strcmp(ansMin, tmp) > 0) strcpy(ansMin, tmp);
    } while(next_permutation(a, a + 10));
    for (int i = 0; i <= n; ++i) cout << ansMax[i]; cout << '\n';
    for (int i = 0; i <= n; ++i) cout << ansMin[i]; cout << '\n';
}

• 참고로 위 코드를 왜 C스타일로 짰냐면, C++의 std::string을 사용하니까 속도가 2배 이상 차이가 나는 바람에 어쩔 수 없었다. 혹시 필요한 분이 있으실까봐 해당 코드도 공유한다.

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

int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    
    char op[n];
    for (int i = 0; i < n; ++i) cin >> op[i];
    
    string ansMax, ansMin;
    for (int i = 0; i <= n; ++i) ansMax.push_back('0'), ansMin.push_back('9');
    do {
    	string tmp = "";
        for (int i = 0; i <= n; ++i) tmp.push_back(a[i] + '0');
        bool valid = true;
        for (int i = 0; i < n; ++i)
            if ((op[i] == '<' && tmp[i] > tmp[i + 1]) ||
		(op[i] == '>' && tmp[i] < tmp[i + 1])) { valid = false; break; }
        if (!valid) continue;
        ansMax = max(ansMax, tmp);
		ansMin = min(ansMin, tmp);
    } while(next_permutation(a, a + 10));
	cout << ansMax << '\n' << ansMin << '\n';
}

Bruteforce - 순열

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

bool check(const vector<int>& num, const vector<char>& op) {
	size_t len = op.size();
	for (size_t i = 0; i < len; ++i) {
		if (op[i] == '<' && num[i] > num[i + 1]) return false;
		if (op[i] == '>' && num[i] < num[i + 1]) return false;	
	} return true;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	int N;
	cin >> N;
	vector<char> op(N);
	for (int i = 0; i < N; ++i) cin >> op[i];
	vector<int> minAns(N + 1), maxAns(N + 1);
	for (int i = 0; i <= N; ++i) minAns[i] = i, maxAns[i] = 9 - i;
	
	// min은 012.. 부터, max는 987.. 부터 순열을 검사하며 부등호 성립 시 탈출한다.
	do { if (check(minAns, op)) break; } while (next_permutation(begin(minAns), end(minAns)));
	do { if (check(maxAns, op)) break; } while (prev_permutation(begin(maxAns), end(maxAns)));
	for (int i : maxAns) cout << i; cout << '\n';
	for (int i : minAns) cout << i; cout << '\n';
}

결과

재귀

조합

순열