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

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

2529번: 부등호

전형적인 백 트래킹 - 브루트포스 알고리즘이다.

구체적인 설명은 생략하나, 만약 다음과 같은 오답을 겪을 경우 참고사항을 적는다.

 

먼저 이 문제는 부등호가 9개까지 사용되어 최대 10자리 수가 나올 수 있으므로, 값의 범위를 잘못 지정할 경우 오답을 겪을 수 있다.

 

1. 런타임 에러 (out of range) 

저장된 문자열을 숫자로 바꾸는 과정에서, 만약 숫자형을 int로 할 경우 겪을 수 있다. int가 아니라 long long으로 바꿔주면 된다.

 

2. 6%에서 틀렸습니다를 겪을 경우

저장된 값을 비교할때 사용되는 maximum값과 minimum값을 확인해보자. 

두 값을 int형으로 저장하면 당연히 틀린다. long long으로 형을 변환해줘야한다.

또한 최대값은 9876543210까지 나올 수 있으므로, 1e4나 2e4로 기본값을 선정할 경우 틀릴 수 있다.

나는 아래처럼 최대값과 최소값을 선정하여 답을 맞출 수 있었다.

pair<string,long long> maxi = {"",-9876543210}; pair<string,long long> mini = {"", 9876543210};

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int k = 0;
pair<string,long long> maxi = {"",-9876543210}; pair<string,long long> mini = {"", 9876543210};
bool ch[10] = {false,};
char c, arr[] = {'0','1','2','3','4','5','6','7','8','9'};
vector<char> v;

void bt(string tx, int index){
    if(tx.size()>k){
        long long temp = stoll(tx);
        if(temp>=maxi.second) maxi = {tx,temp}; 
        if(temp<=mini.second) mini = {tx,temp};
        return; 
    }
    for(int i=0; i<10; i++){
        if(!ch[i]){
            if(index==0){
                ch[i] = true;
                bt(tx+arr[i],index+1);
                ch[i] = false;
            }
            else{
                if(v[index-1]=='>'&&tx[index-1]>arr[i]){
                    ch[i] = true;
                    bt(tx+arr[i],index+1);
                    ch[i] = false;
                }
                else if(v[index-1]=='<'&&tx[index-1]<arr[i]){
                    ch[i] = true;
                    bt(tx+arr[i],index+1);
                    ch[i] = false;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> k;
    for(int i=0; i<k; i++){
        cin >> c;
        v.push_back(c);
    }
    bt("", 0);
    cout << maxi.first << "\n" << mini.first<< "\n";
    return 0;
}