문제

문제 링크

해설

• i - 1번쨰 칸에 고른 숫자와 i - 1번째 부등호가 성립하는 i번쨰 숫자를 고르며 모든 경우의 수를 탐색하는 것이 이 문제의 핵심이었습니다.
• 선택된 숫자는 모두 달라야 한다는 조건이 있기 때문에,
  • visited[10] 이라는 bool 타입 배열을 만들 수도 있고
  • int 타입 매개변수 1개의 10개 하위 bit를 활용해 현재까지 사용한 숫자를 체크할 수도 있습니다.
  • 저는 후자를 사용했지만, 전자를 사용하셔도 전혀 문제 없습니다.
• 0번째 칸은 그냥 0부터 9까지 모든 숫자를 넣을 것입니다.
• 그 전칸과 비교하며 0번째 부등호가 성립하는 숫자부터 차례대로 1번째 칸에 넣습니다.
• 이 과정을 반복하며 총 K + 1개의 숫자를 선택합니다.
  • min(), max() 함수를 이용해서 최댓값과 최솟값을 구할 수 있습니다.
  • 왜냐하면, 모든 숫자가 K + 1 자리수로 똑같기 때문에 단순 문자열 비교 == 숫자 비교이기 때문입니다.
    • (주의하세요! 자릿수가 동일하다는 보장이 없다면 문자열 비교 ≠ 숫자 비교 입니다. 예를 들어 11111 보다 12가 문자열로는 더 큽니다.)

코드

#include <iostream>
using namespace std;

int K;
char sign[10];
string answer_max = "000000000", answer_min = "9999999999";

void solve(string num, int hash, int cnt)
{
    if (cnt == K + 1) {
        answer_max = max(answer_max, num);
        answer_min = min(answer_min, num);
        return;
    }
    for (int i = 0; i < 10; i++) {
        if (hash & (1 << i)) continue;
        int idx = cnt - 1;
        if (cnt == 0 || 
            (sign[idx] == '<' && (num.back() - '0') < i) ||
            (sign[idx] == '>' && (num.back() - '0') > i))
                solve(num + static_cast<char>(i + '0'), hash | (1 << i), cnt + 1);
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> K;
    for (int i = 0; i < K; i++) cin >> sign[i];
    solve("", 0, 0);
    cout << answer_max << '\n' << answer_min << '\n';
    return 0;
}

소스코드 링크

결과