백준 2529번 부등호 - C++ 풀이

---

 

1. 부등호 조건에 맞게 중복 없이 숫자를 하나씩 뽑는다.
2. k+1개를 다 뽑았으면 최대, 최소 정수를 업데이트한다.

 

1. 부등호 조건에 맞게 중복 없이 숫자를 하나씩 뽑는다.

 백트래킹으로 풀 수 있다. 부등호 조건에 맞으면서 중복 사용이 없도록 숫자를 하나씩 뽑아나간다.

 

2. k+1개를 다 뽑았으면 최대, 최소 정수를 업데이트한다.

 부등호가 k개이므로 총 k+1개의 숫자를 뽑아야 한다. 다 뽑았으면 완성된 정수를 구하여 최대, 최소 정수를 업데이트한다. 이때는 문자열을 활용하면 편하다.

 

---

#include <iostream>

using namespace std;

int k;
char signs[10];
int pick[10];
bool is_used[10];
string max_ans = "0000000000", min_ans = "9999999999";

string pickToString() {
    string ret = "";
    for (int i=0; i<=k; i++) {
        ret += pick[i] + '0';
    }
    return ret;
}

void updateAnswer() {
    string ans = pickToString();
    max_ans = max(max_ans, ans);
    min_ans = min(min_ans, ans);
}

void backtrack(int idx) {
    if (idx > k) {
    	updateAnswer();
        return;
    }
    
    for (int i=0; i<10; i++) {
        if (is_used[i]) continue;
        if (signs[idx-1] == '<' && pick[idx-1] > i) continue;
        else if (signs[idx-1] == '>' && pick[idx-1] < i) continue;
        
        is_used[i] = true;
        pick[idx] = i;
        backtrack(idx+1);
        is_used[i] = false;
    }
}

int main()
{
    cin >> k;
    for (int i=0; i<k; i++) cin >> signs[i];
    
    backtrack(0);
    
    cout << max_ans << "\n" << min_ans;

    return 0;
}