[백준 2529번 / C++] 부등호

완전 탐색 문제이다. 

 

#접근 방법 

1. 0부터 9까지 반복문을 돌리는 재귀함수를 생성 후 호출. 
2. 0부터 9까지 반복문을 돌리면서 부등호가 일치한지, 방문 하지 않았는지 체크하고 부합되면 재귀함수 호출.
3. 부등호의 개수를 넘게되면 max값과 min값을 저장하여 리턴. 
4. 스택에 쌓였던 모든 재귀함수가 반환되면 max값과 min값을 출력한다. 

* min 값이 012 일 때는 12 로 출력되니 이럴 경우 앞에 0을 하나 붙여준다.  

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std; 
vector <char> v;
int visited[10], k; 
long long max_n=-1; 
long long min_n=9999999999; 
void dfs(int cnt, string s, int prev) {
	if (cnt == k+1 ) {
		long long x = stoll(s); 
		max_n = max(max_n, x); 
		min_n = min(min_n, x); 
		return; 
	}	
	for (int j = 0; j <= 9; j++) {
		if (visited[j])continue; 
		if (cnt == 0) {
			visited[j] = 1; 
			dfs(cnt + 1, to_string(j), j);		
			visited[j] = 0; 
		}
		else if (v[cnt] == '>'&&!visited[j]&&prev>j) {
			visited[j] =  1;			
			dfs(cnt + 1, s+to_string(j), j);	
			visited[j] = 0; 
		}
		else if (v[cnt] == '<' && !visited[j] && prev < j) {
			visited[j] = 1;	
			dfs(cnt + 1, s + to_string(j), j);
			visited[j] = 0; 
		}
	}
}
int main() {
	 cin >> k; 
	 v.push_back('/'); 
	for (int i = 0; i < k; i++) {
		char c; cin >> c; 
		v.push_back(c); 
	}	
	dfs(0, "", -1); 
	string s1 = to_string(max_n); 
	string s2 = to_string(min_n); 
	if (s1.size() != s2.size()) {
		s2 = '0' + s2; 
	}
	cout << s1 << "\n" << s2; 
}

채점 현황