BOJ 2529. 부등호

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

---

문제 요약

<와 >로 이루어진 부등호 k개(2 ≤ k ≤ 9)가 주어진다. 부등호 사이사이와 양 끝에 0~9 중 서로 다른 숫자 k+1개를 넣어 모든 부등호를 만족시키고, 그 숫자들을 이어 붙여 하나의 수로 읽는다. 이렇게 만들 수 있는 수 중 최댓값과 최솟값을 각각 출력한다. 첫 자리가 0이어도 그대로 k+1자리 문자열로 출력해야 한다는 점이 함정이다. 예를 들어 부등호가 < >라면 가운데 숫자가 양옆보다 커야 하므로, 최댓값은 897, 최솟값은 021이 된다.

---

1. 문제 해석

어떤 문제에서 모든 방법들을 다 해봐야하는데 순서를 사용할 수 있다면, 그 문제는 순열을 이용하여 풀이할 수 있다.

우선, 문제에서 부등호의 개수가 k개이면 들어갈 수 있는 정수의 개수는 k+1개이다. 그리고 k+1개의 자리에 0~9의 서로 다른 정수가 들어가야 한다. 이때 부등호를 만족시키는 최대/최소의 수를 구하는 문제이다.

이 문제는 정수의 순서에 따라 답이 달라지게 되므로, 순서와 관련된 문제이다. 따라서 순열로 풀 수가 있다.

• 부등호 기호 < 와 > 가 나열된 수열 A가 있다. • 기호의 앞뒤에 한 자리 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. • 이때, 선택된 수는 모두 달라야 한다. • k개의 부등호 관계를 모두 만족시키는 (k+1)개 자리의 정수 중에서 최대 값과 최소 값을 구하는 문제

이 문제를 푸는 가장 기본적인 방법은 모든 정수를 다 넣어보고 부등호를 만족시킬 때 기존의 값과 비교하여 최대값 및 최솟값을 갱신하는 것이다.

예를 들어, A = ? < ? > ? < ? 이면 3 < 6 > 5 < 7 이 들어가면 만족한다. 문제의 조건에 따라 생각해보면, 1) 0~9까지의 수 중에서 4개를 고른다. 2) 4개의 수를 모든 순서에 따라 넣어보면서 부등호를 만족하는지 확인한다. 이렇게 두 가지 과정으로 나눌 수 있다.

1) 10개의 수(0 ~ 9) 중에서 k+1 개를 고른다. -> 2^(k+1) 2) (k+1)!개의 순서를 모두 만들고, -> (k+1)! 3) 부등호가 맞는지 검사한다. -> k+1

이때 총 시간복잡도는 2^(k+1) * (k+1)! * (k+1) 이다. k ≤ 9 이면, k + 1 ≤ 10 이므로 시간복잡도는 2^10 * 10! * 10 = 1024 * 3,628,800 * 10 ≒ 36,288,000,000 인데, 이것은 너무 큰 복잡도이다.

---

성능 개선

여기서 시간을 줄이려면 불필요한 탐색을 줄여야한다.

? < ? > ? < ? 에서 3 5 6 7을 골랐다면 3 < 6 > 5 < 7 이 경우에 부등호를 만족하는데, 6 < 8 > 7 < 9 여기서 9 8 7 6으로도 무조건 부등호를 만족시킬 수 있다.

그렇다면 4개의 수를 고르는 과정에서 가장 큰 수 4개를 고르면 무조건 부등호를 만족하는 조합이 있으며, 그 중에서 가장 큰 순열이 전체 중에서 가장 큰 수가 된다. 가장 작은 수도 마찬가지로 생각해볼 수 있다.

부등호에 들어가는 수는 어떤 조합이라도 무조건 부등호를 만족하는 순열이 만들어진다. 따라서 이 문제에서는 수의 대소관계는 중요하지만, 실제로 그 수가 무엇인지는 중요하지 않다. 왜냐하면 이 문제는 가장 큰 수와 작은 수를 찾는 것이기 때문이다.

• k ≤ 9
• k + 1 ≤ 10
• 선택된 숫자는 모두 달라야하기 때문에, 가능한 수의 개수는 10!개 이다
• 모두 해보고, 가장 큰 수와 작은 수를 구해본다.

k+1개의 숫자를 가장 큰수의 구성으로 미리 선택하면 선택하는 시간 2^(k+1)을 없앨 수 있다.

1) 10개의 수(0 ~ 9) 중에서 k+1 개를 고른다. -> 2^(k+1) 2) (k+1)!개의 순서를 모두 만들고, -> (k+1)! 3) 부등호가 맞는지 검사한다. -> k+1

또 다른 예시를 들어보면,

• 입력으로 주어진 부등호가 < > 이고
• 가장 큰 수를 구하는 경우를 생각해보면
• 이 부등호에는 숫자가 총 3개 필요하기 때문에, 가장 큰 숫자 3개인 9, 8, 7로 구성되는 것이 정답임을 알 수 있다.
• 반대로 가장 작은수를 구하는 경우에는 0, 1, 2로 구성되는 것이 정답이 된다.

---

2. 문제 풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool check(vector<int> &perm, vector<char> &a) { // 서로 다른 수가 사이의 부등호를 만족하는지 검사
    for (int i=0; i<a.size(); i++) {
        if (a[i] == '<' && perm[i] > perm[i+1]) {
            return false;
        }
        if (a[i] == '>' && perm[i] < perm[i+1]) {
            return false;
        }
    }
    return true;
}
int main() {
    int k;
    cin >> k;
    vector<char> a(k);
    for (int i=0; i<k; i++) {
        cin >> a[i];
    }
    vector<int> small(k+1);	// the biggest number
    vector<int> big(k+1);	// the smallest number
    for (int i=0; i<=k; i++) {
        small[i] = i;	// 0 ~ k -> 0 1 2 3 ...
        big[i] = 9-i;	// (9 - k) -> 9 8 7 6 ...
    }
    do { // 부등호를 만족하는 가장 작은 수를 찾음 0123 0132 ...
        if (check(small, a)) {
            break;
        }
    } while(next_permutation(small.begin(), small.end()));
    do { // 부등호를 만족하는 가장 큰 수를 찾음 9876 9867 ...
        if (check(big, a)) {
            break;
        }
    } while(prev_permutation(big.begin(), big.end()));
    for (int i=0; i<big.size(); i++) {
        cout << big[i];
    }
    cout << '\n';
    for (int i=0; i<small.size(); i++) {
        cout << small[i];
    }
    cout << '\n';
    return 0;
}