맞춰봐

Problem link: https://www.acmicpc.net/problem/1248

Brute-force로 풀어줄 수 있는데, 사실 계산 복잡도 상으로는 안풀릴 사이즈이지만 엄청나게 많이 프루닝이 된다.

S[i][i]를 보면 A[i]의 부호를 알 수 있으므로 매 단계마다 부호에 따라서 A[i]를 골라보고 S에 위배되지 않는지 확인한다.

• 위배된다면, 재귀를 중단한다.
• 위배되지 않는다면 재귀를 이어나간다.

위배되지 않을 때에만 재귀를 이어나가므로 A[j]를 확정지은 후에는 S[x][j] (for all x < j) 위배 여부만 확인해주면 된다.
(이 부분을 떠올리지 못해서 코드에는 구현하지 않았지만, 그래도 시간 내에 풀린다.)

#include <iostream>
#include <string>

using namespace std;

size_t N;
char MAT[20][20];

bool Verify(const size_t idx, const char mat[][20], int answer[])
{
  static int psum[11];

  psum[0] = 0;
  for (size_t it = 1; it <= idx; ++it)
  {
    psum[it] = psum[it - 1] + answer[it];
  }

  for (size_t it = 1; it <= idx; ++it)
  {
    for (size_t jt = it + 1; jt <= idx; ++jt)
    {
      int sum = psum[jt] - psum[it - 1];
      switch (mat[it][jt])
      {
        case '+': {
          if (sum <= 0)
          {
            return false;
          }
        }
        break;
        case '-': {
          if (sum >= 0)
          {
            return false;
          }
        }
        break;
        case '0': {
          if (sum != 0)
          {
            return false;
          }
        }
        break;
      }
    }
  }

  return true;
}

bool Solve(const size_t idx, const char mat[][20], int answer[])
{
  if (idx > N)
  {
    for (size_t it = 1; it <= N; ++it)
    {
      cout << answer[it] << ' ';
    }
    cout << '\n';

    return true;
  }

  switch (mat[idx][idx])
  {
    case '+': {
      for (int num = 1; num <= 10; ++num)
      {
        answer[idx] = num;
        if (Verify(idx, mat, answer) && Solve(idx + 1, mat, answer))
        {
          return true;
        }
      }

      return false;
    }
    break;
    case '-': {
      for (int num = -10; num <= -1; ++num)
      {
        answer[idx] = num;
        if (Verify(idx, mat, answer) && Solve(idx + 1, mat, answer))
        {
          return true;
        }
      }

      return false;
    }
    break;
    case '0': {
      answer[idx] = 0;
      return Verify(idx, mat, answer) && Solve(idx + 1, mat, answer);
    }
    break;
  }

  return false;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  string mat;
  cin >> N >> mat;

  size_t idx = 0;
  for (size_t it = 1; it <= N; ++it)
  {
    for (size_t jt = it; jt <= N; ++jt)
    {
      MAT[it][jt] = mat[idx++];
    }
  }

  // Solve
  int ANSWER[20];
  Solve(1, MAT, ANSWER);

  return 0;
}