2529 - 부등호

문제

2529번: 부등호

코드

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

int n;
vector<string> ret;
int check[10];
char a[10];

bool possible(char x, char y, char op){
	if(x > y && op == '>')return true;
	if(x < y && op == '<')return true;
	return false;
}

void solve(int idx, string num){
	if(idx == n+1){
		ret.push_back(num);
	}
	
	for(int i = 0; i < 10; i++){
		if(check[i]) continue;
		if(idx == 0 || possible(num[idx-1], i + '0', a[idx-1])){
			check[i] = 1;
			solve(idx+1, num + to_string(i));
			check[i] = 0;
		}
	}
}

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	solve(0, "");
	sort(ret.begin(), ret.end());

	cout << ret[ret.size() -1] << '\n';
	cout << ret[0] << '\n';
}

풀이

하나 고르고 다음거 탐색하는데 다음에 올 수 있는 수가 엄청 많고 다시 돌아가서 반복적으로 탐색해야하니 완전탐색, 백트래킹이라고 볼 수 있었다.
그냥 하나씩 다 해보면 된다.
부등호를 다 탐색하면 return하는 재귀함수를 만든다.
한 식에는 같은 숫자가 들어갈 수 없으므로 check함수로 숫자가 방문한 숫자인지 체크한다.
처음에는 어쩔 수 없이 0부터 9까지 다 넣고 그 다음부터는 부등호 조건에 만족하는 숫자만 탐색하도록 재귀함수를 만든다.
어차피 n+1인 경우에만 ret에 함수를 집어 넣으니 ret에 있는 숫자를 sort한 후에 맨 앞이랑 맨 뒤를 출력하면 된다.

결과

후기

이게 실버 1이라는게 말이안된다고 생각한다.
아직 백트래킹 유형이 어색한건지 재귀함수를 머리로 시뮬레이션 하는게 너무 어렵다.
방문하고 재귀넣고 방문 푸는 이런 느낌을 좀 익혀봐야겠다.