[2529] 부등호

구분

• 백트래킹

 

문제

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

 

 

풀이1

먼저 간단하게, 답 배열에 첫번째 자리 수를 집어 넣어놓고 백트래킹을 진행한다.

진행하고, 최댓값 최솟값 String을 갱신하는 방법이다. 

 

코드(8ms)

//
// 부등호
//

#include <iostream>
#include <vector>

using namespace std;

const int SIZE = 10;

long long min_cost = 999999999999;
long long max_cost = 0;
string minString;
string maxString;

int k;
vector<char> v;
bool check[SIZE];
int num[SIZE];//

bool compare(char c, int a, int b) {

    if (c == '>') {
        return a > b;
    } else if (c == '<') {
        return a < b;
    }
}


void backtracking(int cnt, int first) {

	//k개가 들어오면
    if (cnt == k) {
        string s;

        //num배열에 저장된 내용을 string으로
        for (int i = 0; i <= k; i++) {
            s += to_string(num[i]);
        }

        //최대,최소값 갱신
        if (stoll(s) > max_cost) {
            max_cost = stoll(s);
            maxString = s;
        }
        if (stoll(s) < min_cost) {
            min_cost = stoll(s);
            minString = s;
        }
        return;
    }


    // 현재 부호가 뭔지
    char c = v[cnt];

    for (int i = 0; i < SIZE; i++) {

        //사용 ㄴㄴ && num배열 "부호" 지금 검사중인 수 true일때만
        if (!check[i] && compare(c, num[cnt], i)) {

            //다음 칸에 삽입
            num[cnt + 1] = i;
            check[i] = true;

            backtracking(cnt + 1, first);
            check[i] = false;

        }

    }
    return;


}


int main() {


    cin >> k;
    char op;

    for (int i = 0; i < k; i++) {
        cin >> op;
        v.push_back(op);
    }

	//첫번째 자리수는 채워진 상태로 시작
    for (int i = 0; i < SIZE; i++) {
        num[0] = i;
        check[i] = true;
        backtracking(0, i);
        check[i] = false;
    }

    cout << maxString << "\n";
    cout << minString;
}

원래 이렇게 풀었는데, 더 좋은 방법이 있다고 하셔서 공부해서 나름대로 해보았다..거의 비슷하지만(다음방법)

 

풀이2

그 다음은 최대/최소값의 수가 다음과 같다는 사실에 주목한다.

주어지는 부등호의 수가 k개 라면, 

부등호에 비교되는 숫자는 k+1개 이다.  ( k+1은 최대 0~9까지 이므로 10개이다) 

 

그렇다면, 최대값과 최솟값은 숫자의 배열 순서는 알 수 없지만 , 숫자의 구성은 알 수 있다.

최댓값의 구성은 9부터 차례대로 9, 8, ...  총 k+1개 일 것이며,

최솟값의 구성은 0부터 차레대로 0, 1, ... 총 k+1개로 구성되었을 것이다.

그래서 숫자의 구성을 미리 배열에 넣어두고, 해당 배열에 있는 숫자만 가지고 백트래킹을 진행하는 방식이다.

 

 

코드(0ms)

//
// 부등호
//

#include <iostream>
#include <vector>

using namespace std;

const int SIZE = 10;

int k;
vector<char> v(SIZE);//operator 저장
vector<int> num(SIZE);//백트래킹중 답을 저장할 배열 (최대 0~9)
vector<int> num_list(SIZE);//백트래킹에 사용될 숫자 (최대 0~9)
vector<bool> check(SIZE);//0~9
bool is_end = false;

bool compare(char c, int a, int b) {

    if (c == '>') {
        return a > b;
    } else if (c == '<') {
        return a < b;
    }
}


void backtracking(int cnt) {//사용할 숫자 리스트는 한정되어 있음, 배치만하면됨

    //두개의 if문의 순서가 틀리면 오답 -> k+1일떄도 먼저 검사가 진행되어서 오답인지 확인해야함

    if (cnt > 1 && !compare(v[cnt - 2], num[cnt - 2],
                            num[cnt - 1])) //num에 들어간 숫자 2개 이상이어야 비교 가능, 이미 들어간 두개의 수를 비교해야해서 cnt-2, cnt-1
        return; //오답이라서 탈출
    if (cnt == k + 1) {//숫자 k+1개 다쓰면 종료
        is_end = true;//(진 탈출 조건)
        return;
    }


    for (int i = 0; i <= k; i++) {
        //사용 ㄴㄴ
        if (!check[num_list[i]]) {
            //다음 칸에 삽입
            num[cnt] = num_list[i];
            check[num_list[i]] = true;

            backtracking(cnt + 1);
            if (is_end) return;//진 탈출 조건을 만족하면 진짜로 끝

            //원상복귀
            check[num_list[i]] = false;
            num[cnt] = 0;

        }

    }

}


string arrToString(vector<int> &arr) {

    string ans;
    for (int i = 0; i <= k; i++) {
        ans += to_string(arr[i]);
    }

    return ans;
}


int main() {

    string maxString, minString;

    cin >> k;

    //연산자 입력받기 (k개)
    for (int i = 0; i < k; i++) {
        cin >> v[i];
    }


    //최댓값에 사용될 숫자목록(9부터 k+1개)
    for (int i = 0; i <= k; i++) {
        num_list[i] = 9 - i;
    }
    backtracking(0); //해당 숫자목록을 이용해서 백트래킹 진행
    maxString = arrToString(num);//정답을 string으로


    //초기화
    check.assign(SIZE, false);
    num.assign(SIZE, 0);
    is_end = false;


    //최댓값에 사용될 숫자목록(9부터 k+1개)
    for (int i = 0; i <= k; i++) {
        num_list[i] = i;
    }
    backtracking(0); //해당 숫자목록을 이용해서 백트래킹 진행
    minString = arrToString(num);//정답을 string으로


    cout << maxString << "\n";
    cout << minString;


}

 

 

두 가지 방법은 시간 차이가 확실하다. 

탐색해야하는 숫자의 갯수를 한정지어서 검사할 수 있기 떄문인 것 같다.

첫번째 방법에서는 모든 경우에 0-9를 검사하지만, 두번쨰 방법은 k+1개 내에서 검사한다