백준 2529 부등호

2529번: 부등호 (acmicpc.net)

2529번: 부등호

본 문제의 핵심은 등호가 N 개일 때 조건을 만족하는  N+1 의 숫자는 최소값은 0~N 까지 구성되고 최대값은 9~ (9-N) 까지로 구성된다는 것이다.

 

예를들면 부등식이  < > > 이라면 9,8,7,6 의 조합으로 최대값이 결정된다는 것이다.

최대값 도출은 다음과 같은 계산을 하면 된다.

 

1) 첫자리에 9를 제일 먼저넣어본다 : 9 <

2) 9876 중 9보다 큰 수는 없다. 그럼 다음 큰수는 8 이다 : 8 < 

3) 976 중 8보다 큰수는 9이다 : 8 < 9

4) 76 중 9보다 작은 수는 7 이다 : 8 < 9 > 7

4) 남은 6은 7보다 작다 따라서 정답을 찾았다 : 8 < 9 > 7 > 6

 

좀더 쳬계적으로 생각해보면 9,8,7,6 으로 이루어진 순열 중 큰 순으로 나열하여 하나씩 조건을 맞춰보는것과 동일한 이치이다. 

C++ 의 next_permutation, prev_permutation  함수를 이용하면 모든 순열을 큰순 또는 작은순 으로 찾을 수 있다.

 

구현된 코드는 아래와 같다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

int main()
{
	int nrSign;
	cin >> nrSign;
	
	vector<char>signList;

	for (int i = 0; i < nrSign; i++)
	{
		char tmp;
		cin >> tmp;
		signList.push_back(tmp);
	}

	vector<int> comb;

	for (int i = 9; i >= 9 - nrSign; i--)
	{
		comb.push_back(i);
	}

	do
	{
		if (check(signList, comb)) break;
	} while (prev_permutation(comb.begin(), comb.end()));

	for (auto &c : comb)
		cout << c;
	cout << endl;

	comb.clear();

	for (int i = 0; i <= nrSign; i++)
	{
		comb.push_back(i);
	}

	do
	{
		if (check(signList, comb)) break;
	} while (next_permutation(comb.begin(), comb.end()));

	for (auto &c : comb)
		cout << c;
	cout << endl;
	
	return 0;
}