2529 부등호(재귀 풀이)

 

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

2529번: 부등호

부등호 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

5911

2991

2127

50.463%

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A =>  < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

 

 

<풀이>

1. 문제의 조건에 괄호는 k개, 괄호 사이에 넣을 수 있는 숫자는 총 K+1개이다.

한 자리숫자, 0~9 그리고 두 개의 괄호를 통해 넣을 수 있는 숫자의 가지수는

1,2,3,...,k,k+1 자리마다 각각 10가지, 9가지, 8가지, ...로 10!임을 알 수 있다. 

 

하지만 괄호를 두고 왼쪽 오른쪽 수를 비교함으로써 범위를 축소 할 수 있는 방법도 있다.

 

2.  인덱스 길이를 기준으로 K+1개 수가 놓여져 있다면, 
 그 말은 부등호 관계를 만족하는 수열이 만들어졌다는 의미이고,

인덱스가 0이라는 의미는 어떤수도 올 수 있는 상황 즉, 처음 수를 놓는 상황이다,

 

또한, "0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다." 는 조건을 가지고

중복이 되지 않은 수를 찾아야 하는 의미가 있으므로, 

check 불리언 을 통해 수를 사용했는지 여부를 검사,

 

3. 조건을 만족하기 위해, check 불리언에 false(사용하지 않은 수) 이고,

부등호와, 부등호 를 기준으로 왼쪽 수 < or > 오른쪽 수 를 만족하는 관계의 수들을

모아 최대,최솟값만을 출력한다.

 

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

int arr[]= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
bool check[10];
void go(vector<char> &v, int index);
bool isable(char equal, int n, int i);
int k = 0;
vector<char> ans;
vector<string> str_arr;
string min_string;
string max_string;
int main(void)
{

	cin >> k;

	vector<char> v;
	char ch;
	for (int i = 0; i < k; ++i)
	{
		cin >> ch;
		v.push_back(ch);
	}

	go(v, 0);
	
	cout << str_arr.at(str_arr.size() - 1) << '\n' << str_arr.at(0) << '\n';
	return 0;
}
void go(vector<char> &v, int index)
{
	if (index == k + 1)
	{
		string temp;
		for (int i = 0; i < index; ++i)
		{
			temp += to_string(ans[i]);
		}
		str_arr.push_back(temp);
		return;
	}
		

	//0번 인덱스 예외

	for (int i = 0; i < 10; ++i)
	{
		if (index == 0 || check[i] == false && isable(v[index-1],ans.back(),i))
		{
			check[i] = true;
			ans.push_back(i);
			go(v, index + 1);
			check[i] = false;
			ans.pop_back();
		}
	}

}
bool isable(char equal, int n, int i)
{
	if (equal == '<' && n < arr[i])
		return true;
	
	if (equal == '>' && n > arr[i])
		return true;

	return false;
}