1248

BOJ 1248 Guess 골드3

문제보기

문제

정수로 된 수열 $a_1, a_2, ... , an_n$이 주어지면 $1 \leq i \leq j \leq$에 대해 부호 행렬 S를 정의합니다.

$a_i$부터 $a_j$까지의 합이 0보다 크면 $S_ij$의 부호는 플러스(+)입니다.

• $S_{ij}= + if a_i + ... + a_j > 0$

$a_i$부터 $a_j$까지의 합이 0보다 작으면 $S_ij$의 부호는 마이너스(-) 입니다

• $S_{ij}= - if a_i + ... + a_j < 0$

그 외 $S_ij$는 0입니다.

• $S_{ij}= 0$

예를 들어서 $(a_1, a_2, a_3, a_4) = (-1, 5, -4, 2)$가 주어지면 부호 행렬 S는 다음과 같은 4x4 행렬입니다.

	1	2	3	4
1	-	+	0	+
2		+	+	+
3			-	-
4				+

우리는 정수 수열 $(-1, 5, -4, 2)$는 부호 행렬을 생성한다고 말합니다.

부호 행렬은 정수 수열로 생성될 수 있는 경우 유효합니다.

어떠한 정수 수열이 주어지면 부호 행렬을 쉽게 계산할 수 있습니다. 이 문제는 반대 방향에 관한 것입니다. 유효한 부호 행렬이 주어지면 부호 행렬을 생성하는 정수 수열을 찾으십시오. 두 개 이상의 서로 다른 정수 수열이 동일한 부호 행렬을 생성할 수 있다는 점에 유의하세요. 예를 들어, 수열 (-2, 5, -3, 1)은 수열 (-1, 5, -4, 2)와 동일한 부호 행렬을 생성합니다.

입력

첫 번째 줄에는 정수 $n (1 \leq n \leq 10 )$이 포함됩니다. 여기서 $n$은 정수 수열의 길이입니다. 두 번째 줄에는 $n(n+1)/2$개의 문자로 구성된 문자열이 포함되어 있습니다. 첫 번째 $n$문자는 부호 행렬의 첫 번째 행에 해당되고, 다음 $n-1$문자는 두 번째 행에 해당하고..., 마지막 문자는 문자를 $n$번째 행으로 이동합니다.

출력

부호 행렬을 생성하는 $n$개의 정수 수열을 포함하는 정확히 한 줄을 출력합니다. 둘 이상의 수열이 부호 행렬을 생성하는 경우 그 중 하나를 출력할 수 있습니다. 수열의 모든 정수는 -10에서 10사이(둘다 포함)여야 합니다.

풀이

1. 입력값 받기:

   4
   +-0++--+
   

   첫 번째 줄은 수열의 길이를 나타내는 정수이고 두 번째 줄에는 길이가 (n * (n + 1)) / 2인 문자열이 주어집니다. 이 문자열은 부호 행렬을 나타냅니다. 예를 들어 입력값이 위와 같은 경우 수열의 길이는 4이고 부호 행렬은 "+-0++--+"입니다.

2. 부호 행렬을 2차원 배열로 변환:

   주어진 문자열 형태의 부호 행렬을 2차원 배열로 변환합니다. 이 과정에서 '+'는 1로 '-'는 -1로 '0'은 0으로 변환하여 저장합니다.

3. 재귀 함수를 사용하여 정수 수열 찾기: 재귀 함수를 사용하여 부호 행렬에 대응하는 정수 수열을 찾습니다. 이 과정에서는 각 위치에 들어갈 정수를 찾기 위해 백트래킹을 이용합니다.

   먼저 (n, n) 위치의 부호를 확인하여 해당 위치에 들어갈 정수의 부호를 결정합니다. 그 다음 이전에 결정된 정수들을 기반으로 각 열의 부분합 조건을 만족하는지 확인하여 해당 위치에 들어갈 정수를 찾습니다. 이러한 과정을 모든 위치에 대해 반복하여 올바른 정수 수열을 찾아냅니다.

4. 정수 수열 반환:
   찾은 정수 수열을 문자열로 변환하여 반환합니다. 각 정수 사이에는 공백을 넣어주어야 합니다. 예를 들어, "-1 5 -4 2"와 같은 형태입니다.