백준 2529번: 부등호

[문제 링크]

2529번: 부등호

---

탐욕법과 DFS를 사용하여 풀 수 있었다.

 

부등호를 만족하는 최댓값을 구하기 위해서는 가장 큰 숫자(9)부터 가장 작은 숫자(0) 순으로 조건을 만족하는 숫자를 선택해나가야 한다.

부등호를 만족하는 최솟값을 구하기 위해서는 최댓값과 반대로 가장 작은 숫자(0)부터 가장 큰 숫자(9) 순으로 조건을 만족하는 숫자를 선택해 나가면 된다.

 

최적의 숫자를 선택한 뒤 재귀호출한 결과가 등식을 만족했다면 다른 숫자들은 진행할 필요가 없기 때문에 결과를 반환하도록 구현하였다.

---

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

char arr[10];
bool check[10];

string Greedy(int here, int last, int k, bool ver)
{
	if (here == k) return "";

	string result;

	if (ver)
	{
		for (int i = 9; i >= 0; i--)
		{
			if (result.length() == k - here) 
				return result;

			if (here == -1)
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '>' && last > i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '<' && last < i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
		}
	}
	
	else
	{
		for (int i = 0; i <= 9; i++)
		{
			if (result.length() == k - here) 
				return result;

			if (here == -1)
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '>' && last > i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '<' && last < i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
		}
	}
    
	return result;
}

int main(void)
{
	int k;
	cin >> k;

	for (int i = 0; i < k; i++)
		cin >> arr[i];

	cout << Greedy(-1, 0, k, 1) << endl;
	cout << Greedy(-1, 0, k, 0) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 113 day