2529_부등호

부등호의 개수와 부등호가 입력으로 주어지면

각 위치에 0~9로 구성된 조건을 만족하는 수열을 찾아내어 

그 것을 정수로 환산하여 가장 큰 정수와 가장 작은 정수를 찾는 것이다. 

완전탐색의 방법으로 수행한다. 

다행이도 중복되는 수를 제외하고라는 조건이 있으므로 10^10이 아니라

10! 이다. 10!은 1초안에 1억번 안으로 수행횟수를 조절 할 수 있으므로 충분히 완전탐색 가능한 숫자이다. 

수열을 만들어 나갈 때 

조건을 만족 시키지 않으면 바로 재귀호출을 끊어버리는 방법을 통해 

9개의 부등호를 만드는 재귀적 호출도 금방 수행을 할 수 잇게 된다. 

void make_number(int idx){
    if (idx > 1){
        char operator_idx = relation[idx - 2];
        if (operator_idx == '<'){
            if (result[idx - 2] > result[idx - 1]) return;
        }
        else{
            if (result[idx - 2] < result[idx - 1]) return;
        }
    }
    if (idx == k + 1){
        for (int i = 0; i < idx; i++){
            result_value[result_idx][i] = result[i];
        }
        result_idx++;
        return;
    }
    for (int i = 0; i < 10; i++){
        if (!visited[i]){
            result[idx] = i;
            visited[i] = true;
            make_number(idx + 1);
            visited[i] = false;
        }
    }
}
 

부등호의 위치 인덱스 - 2 와 부등호의 위치 인덱스 - 1의 값이 부등호를 만족시키지 않으면 바로 끊어버리는 코드이다. 

결과값을 출력하는 부분이 다소 애매했는데 이차원 배열을 만들어서 값을 저장하여 출력하는 식으로 답을 도출해내었다.