[백준 1248] 맞춰봐

www.acmicpc.net/problem/1248

1248번: 맞춰봐

 

순열로 풀었다가 틀렸다....

중복 순열로 푸는 문제이다.

n개의 숫자가 모두 같을 수도 있기 때문이다.

 

중복 순열 구현부

선택한 숫자를 cnt 번째 selected 배열에 넣고 다음 턴으로 넘긴다.

 for (int i = -10; i <= 10; i++)
  {
    selected[cnt] = i;
    if (isValid(cnt))
      dfs(cnt + 1);
  }

 

다음 턴으로 넘기기 위해 현재 수열이 조건을 만족하는 지 확인하는 함수가 isValid이다.

(1,1) (1,2) (1,3) (1,4)

       (2,2) (2,3) (2,4)

             (3,3) (3,4)

                   (4,4)

arr에 저장된 값이 이렇게 되어있는데

마지막으로 수열에 채워진 값이 3번째 값이라면 arr의 3번쨰 col에만 영향을 줄 것이다.

따라서 (3,3)부터 거꾸로 (1,3)까지 체크하여 isValid값을 리턴한다.

 

 

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
char arr[11][11];
int n;
int selected[10];
bool flag = false;
char fillArr(int a)
{
  if (a > 0)
  {
    return '+';
  }
  else if (a < 0)
  {
    return '-';
  }
  else
  {
    return '0';
  }
}

bool isValid(int col)
{
  int sum = 0;
  for (int i = col; i >= 0; i--)
  {
    sum += selected[i];

    if (fillArr(sum) != arr[i][col])
    {
      return false;
    }
  }

  return true;
}

void dfs(int cnt)
{
  if (flag)
    return;

  if (cnt == n)
  {
    flag = true;
    for (int i = 0; i < n; i++)
    {
      printf("%d ", selected[i]);
    }
    return;
  }

  for (int i = -10; i <= 10; i++)
  {
    selected[cnt] = i;
    if (isValid(cnt))
      dfs(cnt + 1);
  }
}
int main(void)
{
  scanf("%d", &n);

  char tmp[56];
  scanf("%s", tmp);
  int idx = 0;
  for (int i = 0; i < n; i++)
  {
    for (int j = i; j < n; j++)
    {
      arr[i][j] = tmp[idx++];
    }
  }
  dfs(0);

  return 0;
}