백준 2529 (부등호)

https://www.acmicpc.net/problem/2529

2529번: 부등호

해당 문제는 0 ~ 9 까지 의 숫자들의 순열(중복 X)을 사용하여 주어진 부등호의 경우가 일치할 때 순열에 사용된 숫자를 비교하여 최대값과 최소값을 비교하는 문제이다.

 풀이 :

DFS를 사용한 재귀를 이용하여 문제풀이

1. 규칙 찾기

가장 첫번째 숫자를 제외한 나머지 숫자는 항상 부등호 뒤에 위치한다. 따라서 1 중 for 문을 사용하여 가장 첫 번째 숫자를 넣어준 뒤 재귀함수를 수행시키며 부등호 -> 숫자 순으로 push 시켜주면 된다.

2. 재귀함수로 탐색할 때 부등호와 숫자를 push 하는 과정에서 해당 부등호와 숫자를 넣었을 때 식이 참으로 성립되는지 확인하며 참으로 성립할 때에만 재귀를 진행하며 최적화 시켜준다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;
int k;
vector<char> opList;
vector<char> resList;
int used[11];
long long minn = 999999999999;
long long maxx = -999999999999;
string minStr;
string maxStr;

string resComp(vector<char> nList){
	string str;
	int n = nList.size();
	for (int i = 0; i <= n - 2; i += 2){
		if (nList[i + 1] == '>'){
			if (nList[i] < nList[i + 2]) { str = ""; return str; };
		}
		else{
			if (nList[i] > nList[i + 2]) { str = ""; return str; };
		}
		str.push_back(nList[i]);
	}
	str.push_back(nList[n - 1]);
	return str;
}

long long changNum(string str){
	int n = str.length();
	long long sum = 0;

	for (int i = 0; i < n; ++i){
		sum = sum * 10 + (str[i] - 48);
	}
	return sum;
}

void dfs(int level){
	if (level == k){
		string tmp = resComp(resList);
		long long sum = changNum(tmp);
		if (maxx < sum){
			maxx = sum;
			maxStr = tmp;
		}
		if (minn > sum){
			minn = sum;
			minStr = tmp;
		}
		return;
	}

	for (int i = 0; i <= 9; ++i){
		if (used[i] == 1) continue;
		int n = resList.size();
        // 부등호를 넣었을 때 해당 식이 참일경우에만 재귀 수행
		if (opList[level] == '<'){
			if (resList[n - 1] < (i + 48)){
				used[i] = 1;
				resList.push_back(opList[level]);
				resList.push_back(i + 48);
				dfs(level + 1);
				used[i] = 0;
				resList.pop_back();
				resList.pop_back();
			}
		}
		else{
			if (resList[n - 1] > (i + 48)){
				used[i] = 1;
				resList.push_back(opList[level]);
				resList.push_back(i + 48);
				dfs(level + 1);
				used[i] = 0;
				resList.pop_back();
				resList.pop_back();
			}
		}
	}

}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> k;
	for (int i = 0; i < k; ++i){
		char tmp;
		cin >> tmp;
		opList.push_back(tmp);
	}
    // resList 의 가장 첫번째 숫자 push 후 재귀 수행
	for (int i = 0; i <= 9; ++i){
		used[i] = 1;
		resList.push_back(i + 48);
		dfs(0);
		used[i] = 0;
		resList.pop_back();
	}
	cout << maxStr << endl;
	cout << minStr << endl;
}