[백준/C++] #2529 부등호 (Back Tracking)

문제

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

 

 

구상

주어진 부등호 사이사이에 0~9 범위의 숫자를 넣어야했다. 즉, 부등호 조건에 맞는 0~9로 이루어진 순열을 만들어야 했다. 근데, sign 배열의 크기도 작고, 숫자의 범위로 0~9로 작기에 순열을 만들때 완전탐색으로 backtraking하면 될 것 이라 판단했다. 

 

풀이 + 코드

backtracking의 일반적인 기본 구조는 재귀 함수 안의 if-for문이다. for문 안에서 특정 횟수만큼의 답을 구하거나 답을 구할 수 있도록 반복하는데, for문 안에서 재귀호출을 하며 가능한 경우를 전부 따진다. if문에서는 답이 될 수 있는 조건을 충족하면 답을 따로 저장한다. 세세한 조건은 if문을 사용하는데, for문에서 재귀 돌기 전에 따지거나 if문에서 답 저장하기 전에 따지기도 한다. 

 

재귀함수에는 0~9의 숫자가 쓰였는지의 여부를 used 벡터로 확인해야 하기에 해당 배열과 만든 str타입의 숫자와 숫자 크기를 파라미터로 넣어준다. 그리고, 재귀 호출하는 부분 앞뒤로 used벡터를 갱신해주어야 한다. 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define endl "\n"
using namespace std;
/*
2529 부등호
주어진 부등호 관계에 알맞는 0~9로 이루어진 숫자 배열을 구하자 -> 최대, 최소 정수 모두
k: 2~9 -> brute force 가능
*/

int k;
char signs[9]; // 입력받은 부호들 저장
vector<string> results; // '+' 이용해서 만들꺼면 string으로 해야함

// 주어진 숫자 문자열이 부등호 조건 만족하는지 확인
bool isValid(string num) {
    for (int i = 0; i < k; i++) { // k+1개의 숫자 판단 -> 0 ~ k
        if (signs[i] == '<' && num[i] > num[i+1]) return false; // char끼리도 대소비교 가능
        if (signs[i] == '>' && num[i] < num[i+1]) return false;
    }
    return true;
}

// 재귀로 순열 만들기 (백트래킹) -> if - for문
void generatePermutations(string num, int idx, vector<bool> &used) {
    if (idx == k+1) { // 크기가 되면
        if (isValid(num)) { // 되는지 여부 확인
            results.push_back(num); // 가능한 조합들 result에 넣기
            //cout << num << endl;
        }
        return;
    }
    
    for (int i = 0; i < 10; i++) {
        if (!used[i]) { // 사용한적 없다면 
            used[i] = true; // 사용했다 표시
            generatePermutations(num + to_string(i), idx + 1, used); // 일단 죽이되든 밥이되든 num 만들기
            used[i] = false; // 다시 초기화
        }
    }
}

void solution() {
    vector<bool> used(10, false); // 0~9 사용 여부 저장
    generatePermutations("", 0, used); // 순열 만들기

    sort(results.begin(), results.end()); // 결과 목록 정렬 (오름차순)

    // 출력
    cout << results.back() << endl; // 가장 큰 것
    cout << results.front() << endl; // 가장 작은 것
}

int main() {
    // 입력
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> signs[i];
    }
    
    // 로직
    solution();
    
    return 0;
}