시험기간에 공부안하고 쉬운문제 에디토리얼 쓰는 욱 그 두번째 글입니다

이번 문제는 총19개 팀이 풀어 YES 수로는 4위에 랭크된 문제로 성공률은 25.33%였습니다. 참고로 3위(C)는 20팀, 5위(H)는 18팀이 풀었으니 비교적 쉬운 문제였다고 볼 수 있죠.
잡담을 좀 넣자면 대회 때 저희 팀은 이 문제를 상당히 늦게 잡았었는데, 조금 더 일찍 시도해 보았더라면 좋았을텐데[...] 어려운 건줄 알고..... 그래요.
문제 설명
문제는 간단합니다. 어떤 미지의 정수 수열 a[1], ..., a[n]이 있는데 이 수열의 원소값은 알지 못하고
가능한 모든 구간 (i, j)에 대하여 {a[i]+a[i+1]+...+a[j]} 의 부호(+, 0, -)만을 알려줍니다.
그렇다면 가능한 수열 a[] 를 추론해 내는 것이 문제입니다. 원소의 개수는 10 이하이고, 원소값 또한 -10 이상 10 이하.
풀이
이 문제는 간단한 백트래킹으로 해결할 수 있습니다. 흔히 말하는 '다돌리기'.
가장 단순한 방법은 10¹⁰ 가지의 가능한 경우를 다 해보는 겁니다. -10 이상 10 이하이지만, 원소 하나만의 부호는 알 수 있기 때문에 각 원소의 절대값을 1부터 10까지만 해보면 되겠죠.
10¹⁰ 이라면 시간이 빡빡하긴 한데, 사실 웬만한 인풋에 대해서 구간의 합 sign 을 만족하는 수열은 꽤 많습니다.
어차피 하나만 찾으면 되기 때문에, 실제로 각 원소마다 10개를 다 해보지 않고 어느 몇개만 해도 답이 보통 다 나오더군요-_-a
그리고 도중에 조건을 만족하지 않는 경우에서는 자동으로 가지치기가 되니까, 생각보다 빠른 시간 안에 답을 구할 수 있습니다.
그래서 실제 대회 때는 이렇게 '다 해보기' 를 해서 많은 팀들이 YES를 받을 수 있었습니다.
소스 코드
~~~ cpp

#include
int a[11]; // backtracking 하면서 결정한 수열을 저장
int s[11]; // s[i] = sum{ a[k] }, 1<=k<=i
int sign[11][11];
int n;
char str[1024];
#define sum(x, y) (s[y] - s[x-1]) //sum(x, y) = sum{ a[k] }, x<=k<=y
bool go(int d)
{
// 완성
if(d > n) return true;
// 0인 경우는 바로 다음으로 넘어감
if(sign[d][d] == 0)
{
a[d] = 0; s[d] = s[d - 1];
return go(d+1);
}
for(int i=1; i<=10; ++i)
{
a[d] = sign[d][d] * i;
s[d] = s[d-1] + a[d];
// i 를 시도해 본 후, 가능한가 검사
bool able = true;
for(int j=1; j<=d && able; ++j)
{
if(sign[j][d] ==0 && sum(j, d) != 0) able = false;
if(sign[j][d] < 0 && sum(j, d) >= 0) able = false;
if(sign[j][d] > 0 && sum(j, d) <= 0) able = false;
}
if(able && go(d+1))
return true;
}
return false;
}
int main()
{
int T;
scanf("%d", &T);
while(T-- > 0)
{
scanf("%d %s", &n, str);
int g = 0;
// 입력 루틴
for(int i=1; i<=n; ++i) for(int j=i; j<=n; ++j)
{
if(str[g] == '0') sign[i][j] = 0;
else if(str[g] == '+') sign[i][j] = 1;
else sign[i][j] = -1;
g++;
}
// backtracking
if( go(1) )
{
for(int i=1; i<=n; ++i)
printf("%d ", a[i]);
}
putchar('\n');
}
return 0;
}

<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/53958">원문보기</a>]</div>