백준, BOJ, 2529번, 부등호 C++ [CPP] ★★

전형적인 BruteForce다.

다만. 10자리라는 숫자는 큰 숫자이기에 나같은 범위를 착각하는 실수를 하지 않기를 바란다.

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

int k;
vector<char> vec;

long long maxN = -9999999999; //범위 조심
string MM;
long long minN = 9999999999; //범위 조심
string mm;
bool check[10];

bool IsValid(int a, int b, int seq){
    if(vec[seq] == '>'){
        return a > b;
    }else{
        return a < b;
    }
}

void func(int cnt, string result){
    if(cnt == k+1){
        long long x = stol(result); //범위 조심
        if(x > maxN){
            MM = result;
            maxN = x;
        }
        if(x < minN){
            mm = result;
            minN = x;
        }
        return;
    }
    

    for(int i = 0; i<10; i++){
        if(check[i])continue;
        if(cnt == 0){
            check[i] = true;
            result += to_string(i);
            func(cnt+1, result);
            result.pop_back();
            check[i] = false;
        }else{
            int tmp = result[cnt-1] - '0'; //이전 숫자 tmp, 현재 숫자 i
            if(IsValid(tmp, i, cnt-1)){
                check[i] = true;
                result += to_string(i);
                func(cnt+1, result);
                result.pop_back();
                check[i] = false;
            }else{
                continue;
            }
        }
    }  
}

int main(){
    cin >> k;
    for(int i = 0; i<k; i++){
        char c;
        cin >> c;
        vec.push_back(c);
    }
    

    
    func(0, "");
    
    cout << MM << '\n';
    cout << mm << '\n';
    
    
    
    
    return 0;
}

 

전혀 어렵지 않지만.. 백트래킹 오랜만에 해서..

Check 복원, Result 복원을 하지 않았고..

int 범위도 놓쳤다.. ㅠ

더 풀어야지