[C++ / 백준 1248번] Guess(맞춰봐)

 

백트래킹을 이용해 푸는 문제.

늘상 하던 백트래킹 말고 좋아보이는 방법을 하나 발견할 수 있었는데, 처음에는 N^2 시간복잡도로 풀이하려 했었다.
그 대신 Sum 배열을 선언한 후 합을 미리 구해 놓는 방식이다. 이를 통해 시간복잡도를 획기적으로 줄일 수 있다.
원하는 범위(-10 ~ 10) 까지에서 원하는 Depth 까지 순열을 구한다.
(1, 1), (2,2) (3,3)  ----  이렇게 i == j 일 때는 무조건 자기 자신을 검사하면 되므로

 

if ((sign[depth][depth] == '+' && i <= 0) ||
    (sign[depth][depth] == '-' && i >= 0) ||
    (sign[depth][depth] == '0' && i != 0)) {
    continue;
}

 

이렇게 복잡도를 줄일 수 있다.

그리고 recur() 함수로 재귀 호출을 하기 전에 check() 로 유효성을 검사했다. (훨씬 효율적인 방법이다.)

삼항 연산자 이용

두 번의 삼항 연산자 이용이 있었는데,

 

     sum[depth] = (depth > 0 ? sum[depth - 1] : 0) + i;

 

int tmp = sum[depth] - (i > 0 ? sum[i - 1] : 0);

 

이렇게 두 번이다.

시간 복잡도를 1까지 줄일 수 있는 좋은 방법으로 애용해야겠다.

 

 

#include <iostream>
#include <vector>
using namespace std;

char sign[10][10];

vector<int> seq;
int N;

int sum[10] = { 0 };

bool check(int depth)
{
 
    for (int i = 0; i < depth; i++)
    {

        int tmp = sum[depth] - (i > 0 ? sum[i - 1] : 0);


        if ((tmp >= 0 && sign[i][depth] != '+') ||
            (tmp <= 0 && sign[i][depth] != '-') ||
            (tmp == 0 && sign[i][depth] != '0'))
        {
            return false;
        }

    }
    return true;

}


void recur(int depth)
{
    if (depth == N)
    {
            for (auto i : seq)
            {
                cout << i << " ";
            }
            exit(0);
     
        return;
    }


    for (int i = -10; i <= 10; i++)
    {
        if ((sign[depth][depth] == '+' && i <= 0) ||
            (sign[depth][depth] == '-' && i >= 0) ||
            (sign[depth][depth] == '0' && i != 0)) {
            continue;
        }

            seq.push_back(i);
            sum[depth] = (depth > 0 ? sum[depth - 1] : 0) + i;

            if(check(depth))
                recur(depth + 1);

            seq.pop_back();
            
    }
}


int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = i; j < N; j++)
        {
            cin >> sign[i][j];
        }
    }

    recur(0);   


    return 0;
}