[백준 2529번] 부등호 (C++)

문제링크 : https://www.acmicpc.net/problem/2529

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
char arr[11];
bool visited[11];
string max_s = "";
string min_s = "9876543210";

void dfs(string s)
{
    if(s.size()==n+1)
    {
        max_s = max(max_s, s);
        min_s = min(min_s, s);

        return;
    }

    for(int i=0; i<10; i++)
    {
        if(visited[i]) continue;
        if(arr[s.size()-1] == '>' && s.back()-'0'<i) continue;
        if(arr[s.size()-1] == '<' && s.back()-'0'>i) continue;

        visited[i] = 1;
        s.push_back(i+'0'); //문자로 변환하여 추가
        dfs(s);
        s.pop_back();
        visited[i]=0;
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];

    string s = "";
    for(int i=0; i<10; i++)
    {
        visited[i] = 1;
        s.push_back(i+'0'); //문자로 변환하여 추가
        dfs(s);
        s.pop_back();
        visited[i]=0;
    }

    cout << max_s << "\n";
    cout << min_s << "\n";

    return 0;
}

 

문자열 방식의 백트래킹 문제이다.

부등호에 따라 뒤에 숫자를 추가해야하기 때문에 문자열로 하여 더해주었다.

다만 반복문에서는 0~9까지로 체크하기 때문에 기존 문자열에서 맨 뒤의 값을 숫자로 변환하여 크고 작은지 체크하고,

문자열에 넣을 때는 0~9까지 문자열에 추가해야 하기 때문에 문자로 변환하는 과정이 필요하다.