1. 문제설명

부등호의 개수와 어떤 부등호인지 주어진다.
해당 부등호를 만족하는 숫자를 찾아라.
- 선택된 숫자는 모두 달라야 한다.
만족하는 숫자 조합의 최대, 최소 정수를 각각 출력하라.

2. 알고리즘 설계

백트래킹 + 브루트포스 문제이다.
DFS로 하나씩 넣어보는 구현을 할 수도 있겠지만,
이 문제에서는 permutation을 사용하였다.

3. 로직

next_permutation
- 오름차순으로 정렬된 수열에서 모든 조합을 뽑는다.
- 돌다가 특정 조건을 주어 멈추게 되면,
  - 해당 수열의 조합으로 저장이 되어 있다.
    - 예를 들어, [1,2,3,4]의 조합을 추출하다가,
    - [4,2,1,3]에 반복을 멈추면 해당 수열로 저장된다.
prev_permutation
- 내림차순으로 정렬된 수열에서 모든 조합 추출.
- 나머지 내용은 상기 내용과 동일
next_permutation의 조합 중 최초로 조건이 맞다면 최소
prev_permutation의 조합 중 최초로 조건이 맞다면 최대
조합을 뽑을 때마다 부등호 조건이 맞는지 구현하면 된다.

4. 전체 코드

#include<bits/stdc++.h>
using namespace std;

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int k; cin >> k;

	vector<char> v(k);
	for (int i = 0; i < k; i++)
		cin >> v[i];

	vector<int> small(k + 1);
	vector<int> big(k + 1);

	for (int i = 0; i <= k; i++) {
		small[i] = i;
		big[i] = 9 - i;
	}

	do {
		if (check(big, v)) break;
	} while (prev_permutation(big.begin(), big.end()));

	do {
		if (check(small, v)) break;
	} while (next_permutation(small.begin(), small.end()));
	
	for (int n : big) cout << n;
	cout << '\n';
	for (int n : small) cout << n;

	return 0;
}

5. 소감

거의 대부분은 이미 라이브러리화 되어 있구나를 느낌.
예전에 문제풀 때 발견했는데, binary_search도 함수가 있음.

BOJ 2529. 부등호

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드

5. 소감