[C/C++] 코드업(codeup) 4745번 부등호

▽문제 바로가기

https://codeup.kr/problem.php?id=4745

부등호

---

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다.

그 다음 줄에는k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다.

k 의 범위는2<=k<=9 이다. 

 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다.

단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다.

모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

 

문제 풀이

 

입출력의 결과를 보면 어느정도 규칙이보입니다. 하지만 백트래킹으로 풀어봤습니다.

 

1. 완전탐색구현

2. 불필요한 탐색 줄이기

 

이번 문제에서 특히 조심해야 하는 부분은 출력에서 "출력 정수는 하나의 문자열이 되도록 해야 한다." 입니다.

또한 입력받을시 "부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다." 라고 명시되어있습니다. '%*c'를 사용하면 안되고 cin으로 입력받으니 잘 됬습니다.

 

#include <stdio.h>
#include <iostream>

using namespace std;

int k;
char arr[12];
int cache[12] = {0,};
long long int myMax = -9876543210;
long long int myMin = 9876543210;
char maxCache[12];
char minCache[12];

bool isPromising(int i, int index){
	if(index==0) return true;
	
	for(int j=0;j<index;j++){
		if(cache[j]==i) return false;
	}
	
	if(arr[index-1]=='<'){
		if(cache[index-1]>i) return false;
	}
	
	if(arr[index-1]=='>'){
		if(cache[index-1]<i) return false;
	}
	
	return true;
}

void backtracking(int index, long long int num){
	
	if(index==k+1){
		if(myMax<num){
			myMax = num;
			for(int i=0;i<index;i++) maxCache[i] = cache[i]+48;
		}
		
		if(myMin>num){
			myMin = num;
			for(int i=0;i<index;i++) minCache[i] = cache[i]+48;
		}
		return;
	}
	
	for(int i=0;i<10;i++){
		if(isPromising(i, index)){
			cache[index] = i;
			backtracking(index+1, num*10+i);
		}
	}
		
}


int main(){
	
	scanf("%d\n", &k);
	for(int i=0;i<k;i++){
		//scanf("%c%*c", &arr[i]);
		cin >> arr[i];
	}
	
	backtracking(0, 0);
	
	long long int div = 1;
	for(int i=0;i<k;i++){
		div *= 10;
	}

	for(int i=0;i<=k;i++) printf("%c", maxCache[i]);
	printf("\n");
	for(int i=0;i<=k;i++) printf("%c", minCache[i]);
	
	return 0;
}