백준 2529. 부등호

알고리즘 기초 문제 중 브루트포스-재귀 문제(530)

부등호

1. 간단 설명

“부등호 관계를 만족시키는 정수”

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다

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

부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 (3456128790)

이 수를 주어진 부등호 관계를 만족시키는 정수

그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다

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

제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값 구하기

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.

2. 예시

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

3456128790은 <<<><<><>의 부등호를 만족시키는 정수 중 하나이다

이 부등호를 만족시키는 정수 중 최대값은 6789345120

최소값은 0124357698이다 (0이 앞에 올 수 있음)

3. 알고리즘

백트래킹을 통해 수를 생성하고, 해당 수가 부등호를 만족하는 정수인지 체크하는 방법을 사용했다

재귀 함수 (int level, string num)
	생성한 수가 k+1 자리라면
		부등호를 만족하는 정수인지 체크
			만족한다면 최대값, 최소값을 갱신
	
	0~9까지 수 중에 사용하지 않은 수 선택

	이 수를 사용 표시 체크하고, 
	부등호 관계를 만족하는 정수의 맨 뒷자리에 추가하기
	
	재귀 호출

	선택해제
	맨뒷자리 빼기

필요 변수

• 부등호의 개수 int k 2 ≤ k ≤ 9
• 부등호를 저장할 문자열 string sign
• bool used[10] <- 0123456789 가 사용되었는지 체크하는 변수
• 부등호 관계를 만족시키는 정수의 최대 최소값 long long int max_val, min_val
  • 최대 98 7654 3210이므로, int형으로 처리 불가!

4. 소스코드

#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip> // setw 를 통해 cout 출력포멧 지정

using namespace std;

int k;
string sign;
bool used[11];

long long int max_val = -21e10, min_val = 21e10;

// 부등호 관계를 만족시키는 정수인지 체크하는 함수
bool check(string num) {

	for (int i = 0; i < k; i++) {
		//i와 i+1에 부등호를 넣어봄
		int tmp1 = (num[i] - '0');
		int tmp2 = (num[i + 1] - '0');
		
		// 부등호 관계가 성립하지 않으면 바로 false 리턴
		if (sign[i] == '<' && (tmp1 >= tmp2)) {
			return false;
		}
		else if(sign[i] == '>' && (tmp1 <= tmp2)){
			return false;
		}
	}
	return true;
}

void recursive(int level, string num) {
	if (level == k+1) {
		if (check(num)) {
			long long int n = stoll(num); // stoi가 아닌 stoll 사용에 주의!
			min_val = min(min_val, n);
			max_val = max(max_val, n);
		}
		return;
	}

	for (int x = 0; x <= 9; x++) {
		if (used[x] == 1) continue;
		used[x] = true;
		num.push_back(x + '0');
		recursive(level + 1, num);
		used[x] = false;
		num.pop_back();
	}

}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> k;
	
	for (int i = 0; i < k; i++) {
		char ch; cin >> ch;
		sign.push_back(ch);
	}

	recursive(0, "");

	cout << setw(k + 1) << setfill('0') << max_val << '\n';
	cout << setw(k + 1) << setfill('0') << min_val << '\n';

	return 0;
}

배운점

1. setw로 몇자리 까지 출력할건지 정한 뒤, setfill로 0으로 채울 수 있다
   • 또한 printf 함수도 printf("%0*d, k, max_val)과 같이 처리해서 k자리 수를 0으로 채워서 출력 가능함
2. stoi out of range에러. stoll 사용에 주의
3. 무지성으로 최대 최소값을 21e8로 초기화했는데, 문자열로 큰 정수 값을 처리할 때 주의할 것!

배운게 많은 문제였다