def check(index):
s = 0
for i in range(index, -1, -1):
s += ans[i]
if sign[i][index] == 0:
if s != 0:
return False
elif sign[i][index] < 0:
if s >= 0:
return False
elif sign[i][index] > 0:
if s <= 0:
return False
return True
def go(index):
if index == n:
return True
if sign[index][index] == 0:
ans[index] = 0
return check(index) and go(index + 1)
for i in range(1, 11):
ans[index] = i * sign[index][index]
if check(index) and go(index + 1):
return True
return False
n = int(input())
s = input()
sign = [[0] * n for _ in range(n)]
ans = [0] * n
cnt = 0
for i in range(n):
for j in range(i, n):
if s[cnt] == '0':
sign[i][j] = 0
elif s[cnt] == '+':
sign[i][j] = 1
else:
sign[i][j] = -1
cnt += 1
go(0)
print(' '.join(map(str, ans)))
"""
-10 ~ 10 까지 N개의 정수로 이루어진 수열 A (N <= 10)
S[i][j] = A[i] ~ A[j] 까지의 합,
S[i][j]가 0보다 크면 +, 작으면 -, 같으면 0을 출력
S가 주어졌을 때, 가능한 A를 찾는 문제
각 자리마다 21가지의 수를 구해 넣어주저야 함
O(21^10)은 너무 큰 수로 BRUTE FORCE로는 해결이 어려움
----시간초과를 해결 할 방법 첫번째----
s[i][i] = A[i]의 부호
s[i][i] > 0 1~ 10
= 0 0
< 0 -10 ~ -1
로 경우의 수를 10^10로 줄일 수 있다.
하지만 10^10은 100억으로 시간초과.
----두번째----
i번째의 수를 정하면 S[j][i]의 부호를 모두 검사할 수 있다.
"""
일반적으로 재귀함수에서 더 이상의 호출이 의미 없을 때, 중간에 재귀함수를 중단시키는 알고리즘을 의미한다.
백준 14889번, 15661번 스타트 링크 문제를 통해 백트래킹에 대해 알아보자.
1 ~ N까지의 번호 중 2개의 팀을 각 N/2명으로 나누어야 한다.
2. 이때 S[I][J] = i번 사람과 j번 사람이 같은 팀일 때 팀에 더해지는 능력치이다.
3. 팀의 능력치 : 팀에 속한 모든 s[i][j]쌍의 합이다.
4. 문제 요구 사항 : 두 팀의 능력치를 구하고 차이의 최소를 구하라
해당 문제를 요구 사항에 맞게 코딩하면
def go(index, first, second):
if index == n:
if len(first) != n // 2:
return -1
if len(second) != n // 2:
return -1
t1 = 0
t2 = 0
for i in range(n // 2):
for j in range(n // 2):
if i == j:
continue
t1 += s[first[i]][first[j]]
t2 += s[second[i]][second[j]]
diff = abs(t1 - t2)
return diff
ans = -1
t1 = go(index + 1, first + [index], second)
if ans == -1 or (t1 != -1 and ans > t1):
ans = t1
t2 = go(index + 1, first, second + [index])
if ans == -1 or (t2 != -1 and ans > t2):
ans = t2
return ans
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
print(go(0, [], []))
이런 코드가 나오게 된다.
index : 사람을 어떤 팀에 넣을지 (스타트 팀, 링크 팀)
first : 1번 팀, second : 2번 팀
index == n 일 경우 함수 종료
first나 second의 팀 수가 n//2를 넘어가게 되면(딱 절반이어야 하는데 넘어갈 때) -1 반환
하지만 index == n 일때
first나 second가 n//2가 아님을 검사하게 되면
결국 index는 n 만큼의 재귀를 실행하게 된다.
만약 first나 second가 (n이 8일 때) 5를 넘었을 때 바로 종료한다면 더 시간을 단축할수 있을 것이다.
이때를 위해 백트래킹 방법이 사용된다.
재귀 중간에, 특정 상황(의미 없는 재귀가 반복된다고 판단)에서 재귀를 종료시키는 구문을 넣어준다.
def go(index, first, second):
if index == n:
if len(first) != n // 2:
return -1
if len(second) != n // 2:
return -1
t1 = 0
t2 = 0
for i in range(n // 2):
for j in range(n // 2):
if i == j:
continue
t1 += s[first[i]][first[j]]
t2 += s[second[i]][second[j]]
diff = abs(t1 - t2)
return diff
ans = -1
if len(first) > n // 2:
return -1
if len(second) > n // 2:
return -1
t1 = go(index + 1, first + [index], second)
if ans == -1 or (t1 != -1 and ans > t1):
ans = t1
t2 = go(index + 1, first, second + [index])
if ans == -1 or (t2 != -1 and ans > t2):
ans = t2
return ans
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
print(go(0, [], []))
따라서 중간에
if len(first) > n // 2:
return -1
if len(second) > n // 2:
return -1
from itertools import product
n, m = map(int, input().split())
data = [i for i in range(1, n + 1)]
for i in product(data, repeat = m):
for j in i:
print(j, end=' ')
print()
파이썬 라이브러리 itertools의 combinations을 이용하여 손쉽게 풀 수 있는 문제.
from itertools import combinations
n, m = map(int, input().split())
data = [i for i in range(1, n + 1)]
for i in combinations(data, m):
for j in i:
print(j, end=' ')
print()
