BOJ 2529 : 부등호 - C++

부등호

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int N;
int arr[10];
bool isused[10];
string c[10];
vector<string> ans;
void func(int depth){
    if(depth == N){
        string tmp = "";
        for(int i=0;i<=N;i++)
            tmp+=to_string(arr[i]);
        ans.push_back(tmp);
    }else{
        for(int i=0;i<=9;i++)
        {
            if(isused[i]) continue;
            string t = c[depth];
            bool flag;
            if(t == "<"){
                flag = arr[depth] < i ? true : false;
            }else{
                flag = arr[depth] > i ? true : false;
            }
            if(!flag) continue;
            isused[i] = true;
            arr[depth+1] = i;
            func(depth+1);
            isused[i] = false;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
        cin >> c[i];
    for(int i=0;i<=9;i++)
    {
        isused[i] = true;
        arr[0] = i;
        func(0);
        isused[i] = false;
    }
    sort(ans.begin(), ans.end());
    cout << ans.back() << '\n';
    cout << ans.front() << '\n';
}
  • 로직
    : 조건에 맞게 백트래킹을 수행하면 된다
    (입력이 10보다 작기때문에 충분히 가능)

좋은 웹페이지 즐겨찾기