[🐉 백준 13단계] 백트래킹

 

백트래킹: 조건에 따른 모든 조합의 수를 찾는 것.

 

15649

import itertools

a, b = input().split()
l = [i for i in range(1, int(a)+1)]
s = list(itertools.permutations(l, int(b)))

for s in s:
  a = ''
  for i in s:
    a += str(i)
    a += ' '
  print(a)

 

15650

import itertools

a, b = input().split()
l = [i for i in range(1, int(a)+1)]
s = list(itertools.combinations(l, int(b)))

for s in s:
  a = ''
  for i in s:
    a += str(i)
    a += ' '
  print(a)

 

15651

import itertools

a, b = input().split()
l = [i for i in range(1, int(a)+1)]
s = list(itertools.product(l, repeat=int(b)))

for s in s:
  a = ''
  for i in s:
    a += str(i)
    a += ' '
  print(a)

 

15652

import itertools

a, b = input().split()
l = [i for i in range(1, int(a)+1)]
s = itertools.combinations_with_replacement(l, int(b))

for i in s:
    print(' '.join(map(str, i)))

 

9663

 

2580

 

14888

 

14889

import itertools

team = []
n = int(input())
n_list = [i for i in range(n)]

for _ in range(n):
  team.append(list(map(int, input().split())))

c = list(itertools.combinations(n_list, n//2))

c1 = c[:len(c)//2]
c2 = c[len(c)//2:]
c2 = c2[::-1]

answer1 = []
answer2 = []

#  스타트팀
for i in c1:
  s = 0
  for j in range(len(i)-1):
    for k in range(j+1, len(i)):
      a = i[j]
      b = i[k]
      s += team[a][b] + team[b][a]
  answer1.append(s)

# 링크팀
for i in c2:
  s = 0
  for j in range(len(i)-1):
    for k in range(j+1, len(i)):
      a = i[j]
      b = i[k]
      s += team[a][b] + team[b][a]
  answer2.append(s)


answer = []
for i in range(len(answer1)):
  if answer1[i] > answer2[i]:
    answer.append(answer1[i]-answer2[i])
  else:
    answer.append(answer2[i]-answer1[i])

print(min(answer))