[코드업 3540] 0 만들기 게임

1~N까지 차례대로 적힌 수열에서 연산자들을 선택하여 전체 계산결과가 0이 되도록 만드는 문제이다. 문제 분류가 백트래킹으로 되어 있는만큼 전형적인 백트래킹 기법으로 풀이가 가능하다. 시간을 많이 허비했는데 적절한 자료구조와 c++ 벡터에서 요소를 지우고 난 후에 인덱스를 어떻게 처리할 것인지 로직구성에 애를 먹었다. 

 

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

vector<char> opers;
char oper[3] = {' ', '+', '-'};

int calculate(int N) {
    vector<int> tmp;
    vector<int> eraseIdx;
    deque<int> numbers;

    // 임시 숫자 배열생성
    for (int i = 1; i <= N; i++) {
        tmp.push_back(i);
    }   
    
    // 공백연산 처리
    int numIdx = 0;
    for (int i = 0; i < opers.size(); i++) {
        if (opers[i] == ' ') {
            tmp[numIdx] = tmp[numIdx] * 10 + tmp[numIdx+1];
            tmp.erase(tmp.begin() + (numIdx + 1));
        }
        else {
            numIdx++;
        }
    }

    // 실제 계산할 숫자 삽입
    for (int num : tmp) {
        numbers.push_back(num);
    }
    
    // 연산 수행
    for (char op : opers) {
        if (op == ' ') {
            continue;
        }
        else if (op == '+') {
            int a = numbers.front();
            numbers.pop_front();

            int b = numbers.front();
            numbers.pop_front();

            int num = a + b;
            numbers.push_front(num);
        }
        else if (op == '-') {
            int a = numbers.front();
            numbers.pop_front();

            int b = numbers.front();
            numbers.pop_front();

            int num = a - b;
            numbers.push_front(num);
        }
    }

    return numbers.front();
}

// 연산자를 백트래킹 방식으로 선택한다.
void makeZero(int idx, int cntOper, int N) {
    if (idx == cntOper) {
        if (calculate(N) == 0) {
            for (int i = 0; i < opers.size(); i++) {
                cout << (i+1);
                cout << opers[i];
            }
            cout << N << endl;
        }
        return;
    }

    for (char op : oper) {
        opers.push_back(op);
        makeZero(idx+1, cntOper, N);
        opers.pop_back();
    }
}

int main() {
    int N;
    cin >> N;

    // 재귀함수 호출
    makeZero(0, N-1, N);

    return 0;
}

 

더 좋은 방법을 찾도록 노력해봐야겠다. 주어진 조건에 따라 최적의 자료구조가 어떤 것일지 생각해보는 연습도 필요하다.