부등호 (feat. 백준, 2529번)

부등호
https://www.acmicpc.net/problem/2529

2529번: 부등호

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <set>
#include <string.h>
using namespace std;
int N;
char sign[10];
bool visit[10];
set<string> ans;
void dfs(register int v, register int cnt, string str){
    if(cnt == N){
        ans.insert(str);
        return;
    }
    for(register int i = 0; i < 10; ++i)
        if(!visit[i]){
            if(sign[cnt] == '<' && v >= i)
                continue;
            else if(sign[cnt] == '>' && v <= i)
                continue;
            visit[i] = true;
            dfs(i, cnt + 1, str + to_string(i));
            visit[i] = false;
        }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(sign, 0, sizeof(sign));
    cin >> N;
    for(register int n = 0; n < N; ++n)
        cin >> sign[n];
    memset(visit, false, sizeof(visit));
    for(register int i = 0; i < 10; ++i){
        visit[i] = true;
        dfs(i, 0, to_string(i));
        visit[i] = false;
    }
    cout << *ans.rbegin() << "\n" << *ans.begin();
    return 0;
}
// *&)*@*

 

1. 중복되는 수는 올 수 없으므로 방문 flag (visit 변수) 를 두어야 합니다.
2. 부등호를 기준으로 앞과 뒤가 결정되며 dfs 수행 이후에는 위 방문 flag를 초기화 해야 합니다. (그래야 다음번에 해당 숫자가 사용될 수 있습니다.)