[BaekJoon] 2529 부등호 :: monton

문제

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

풀이

이 문제는 모든 경우의 수를 완전 탐색 해야하므로 dfs를 사용!

visit 함수를 사용해서 0~9까지 각 수를 한번만 포함하는 K+1개의 숫자를 만들었다

min과 max를 배열로 지정한 이유는 min에서 맨앞의 자리수가 0일수도 있기 때문이다

지저분하게 짰는데 나중에 다시 보아야 겠다

코드

#include <iostream>
using namespace std;
 
int K;
char arr[11];
int Min[11], Max[11],visit[11],temp[11];
 
void copyarr(int arr[],int temp[]) {
    for (int i = 0; i < K + 1; i++) arr[i] = temp[i];
}
 
void func(int num,int cnt,int n) {
    if (cnt == K) {
 
        //현재값이 min, max 값과 비교하여 적절히 바꿔주기
        int flag = 0;
        for (int i = 0; i < K + 1; i++) {
            if (Max[i] > temp[i]) break;
            if (Max[i] == temp[i]) continue;
            copyarr(Max, temp);
        }
 
        for (int i = 0; i < K + 1; i++) {
            if (Min[i] < temp[i]) break;
            if (Min[i] == temp[i]) continue;
            copyarr(Min, temp);
        }
        return;
    }
 
    for (int i = 0; i < 10; i++) {
        if (!visit[i]) {
            visit[i] = 1;
 
            if (arr[n] == '<'&&num < i) temp[cnt+1]=i, func(i, cnt + 1, n + 1);
            if (arr[n] == '>'&&num > i) temp[cnt+1] = i, func(i, cnt + 1, n + 1);
            
            visit[i] = 0;
        }
    }
}
 
int main() {
    cin >> K;
    for (int i = 0; i < K; i++) cin >> arr[i];
    for (int i = 0; i < K + 1; i++) Min[i] = 9, Max[i] = 0;
 
    for (int i = 0; i < 10; i++) temp[0] = i, visit[i] = 1, func(i, 0, 0), visit[i] = 0;
 
    for (int i = 0; i < K + 1; i++) cout <<Max[i];
    puts("");
    for (int i = 0; i < K + 1; i++) cout << Min[i];
 
}