백준 2529번. 부등호 (C언어)

백준 2529번 부등호 문제입니다.

자세한 문제내용은 글을 읽어보시길 바랍니다.

www.acmicpc.net/problem/2529

접근방법

---

처음 문제를 풀려고 할 땐 딱히 떠오르는 방법이 없어서 매우 고민했던 문제입니다.

각 부등호의 개수에 따라서 최대값, 최대값을 정해서.. 어쩌고 저쩌고 생각을 많이 해봤는데,

답이 잘 안나와서 일단 문제를 다시 차분히 읽어봤습니다.

 

그랬더니 문제에서 부등호 k의 범위가 최대 9까지라고 했고, 즉 숫자는 최대 10개이기 때문에

모든 경우의 수를 다 검사하는 완전탐색으로 풀리지 않을까 생각했습니다.

int main() {
	int k, i;
	scanf("%d", &k);
	for (i = 0; i <= k; i++) {
		if (i != k) {
			getchar();
			str[i] = getchar();
		}
		else str[i] = NULL;
		max[i] = '9' - k + i;
		min[i] = '0' + k - i;
	}

먼저 부등호의 개수 k를 입력받고, 각각 부틍호를 저장할 배열,

최대값을 저장할 배열, 최소값을 저장할 배열에 값을 저장해줍니다.

이 배열들(str, max, min)은 모두 외부변수로 선언했습니다.

void swap(int a, int b) {
	char tmp;
	tmp = copy[a];
	copy[a] = copy[b];
	copy[b] = tmp;
}
void bf(int flag, int n) {
	if (n == 1) {
		if (check()) {
			if (flag) {
				if (strcmp(max, copy) < 0) {
					strcpy(max, copy);
				}
			}
			else {
				if (strcmp(min, copy) > 0) {
					strcpy(min, copy);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		swap(i, n - 1);
		bf(flag, n - 1);
		swap(i, n - 1);
	}
}

이후 재귀함수인 bf를 사용해서 모든 경우의 수를 다 비교해서 최대값의 경우

이전의 값보다 더 크면 교환, 최솟값의 경우 그 반대일 경우 값을 교환하도록 했습니다.

이때 모든 경우의 수를 검사할 배열은 copy배열에 기존 max,min배열의 값을 복사해서 사용했습니다.

int check() {
	for (int i = 0; i < strlen(str); i++) {
		if (str[i] == '<') {
			if (copy[i] >= copy[i + 1]) {
				return 0;
			}
		}
		else if(str[i] == '>'){
			if (copy[i] <= copy[i + 1]) {
				return 0;
			}
		}
	}
	return 1;
}

 해당 숫자가 주어진 부등호에 부합하는지 확인하면서,

도중에 맞지 않으면 바로 return하여 시간을 최소화 하도록 하였습니다.

strcpy(copy, max);
bf(1, k+1);
strcpy(copy, min);
bf(0, k + 1);
printf("%s\n%s", max, min);

마지막으로 함수의 수행 결과를 화면에 출력해주면 끝입니다.

전체 소스코드는 아래에 있습니다.

#include<stdio.h>
#include<string.h>

void swap(int a, int b);
void bf(int flag, int n);
int check();

char str[11], max[11], min[11], copy[11];

int main() {
	int k, i;
	scanf("%d", &k);
	for (i = 0; i <= k; i++) {
		if (i != k) {
			getchar();
			str[i] = getchar();
		}
		else str[i] = NULL;
		max[i] = '9' - k + i;
		min[i] = '0' + k - i;
	}
	max[i] = NULL;
	min[i] = NULL;
	strcpy(copy, max);
	bf(1, k+1);
	strcpy(copy, min);
	bf(0, k + 1);
	printf("%s\n%s", max, min);
    	return 0;
}

void swap(int a, int b) {
	char tmp;
	tmp = copy[a];
	copy[a] = copy[b];
	copy[b] = tmp;
}
void bf(int flag, int n) {
	if (n == 1) {
		if (check()) {
			if (flag) {
				if (strcmp(max, copy) < 0) {
					strcpy(max, copy);
				}
			}
			else {
				if (strcmp(min, copy) > 0) {
					strcpy(min, copy);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		swap(i, n - 1);
		bf(flag, n - 1);
		swap(i, n - 1);
	}
}
int check() {
	for (int i = 0; i < strlen(str); i++) {
		if (str[i] == '<') {
			if (copy[i] >= copy[i + 1]) {
				return 0;
			}
		}
		else if(str[i] == '>'){
			if (copy[i] <= copy[i + 1]) {
				return 0;
			}
		}
	}
	return 1;
}