[백준 2529] 부등호

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

 

부등호의 순서가 주어질 때 각 부등호 사이에 0 ~ 9까지의 숫자를 한번씩 사용해서 부등호의 식을 만족하는 수의 순서를 출력하는 문제이다

 

문제를 보자마자 백트래킹이 생각났는데 N이 10일 때 최악의 경우 0123456789 ~ 987654321까지 모든 경우의 수를 다 찾아 부등호의 관계를 비교하는 것은 무조건 시간 초과에 걸릴 것 같았다.

 

그래서 중간중간에 가지치기를 이용해 필요 없는 구간은 전부 스킵하는 과정이 필요했다.

 

부등호의 위치와 현재 선택된 수를 기준으로, 다음에 와야 되는 수와 대/소 비교를 해 부등호의 식과 틀리게 된다면 건너뛰는 방법을 선택했다.

 

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
using namespace std;
int N;
char c[10];
bool selected[10];
int arr[10];
string mn, mx;
void backTrack(int cnt);
int main() {
    FASTIO
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> c[i];
    }
    mx = "000000000";
    mn = "999999999";
    for(int i = 0; i <= 9; i++) {
        fill(arr, arr + 10, -1);
        selected[i] = true;
        arr[0] = i;
        backTrack(1);
        selected[i] = false;
    }

    cout << mx << '\n' << mn;
}
void backTrack(int cnt) {
    if(cnt == N + 1) {
        string k;
        for(int i = 0; i < cnt; i++) {
            k += to_string(arr[i]);
        }
        mx = max(k, mx);
        mn = min(k, mn);
        return;
    }
    for(int i = 0; i <= 9; i++) {
        if(selected[i]) continue;
        if(c[cnt - 1] == '>' && arr[cnt - 1] < i) continue;
        if(c[cnt - 1] == '<' && arr[cnt - 1] > i) continue;
        selected[i] = true;
        arr[cnt] = i;
        backTrack(cnt + 1);
        selected[i] = false;
    }
}