사용 언어: python 3.9.1

❓ Problem

백준 14889: 스타트와 링크

📕 피드백

1. 발전 방향

비트마스크 공부해야겠다.

2. 느낀점

너무 오래 걸려서 풀었는데, 역시 처음부터 아이패드로 풀었어야 했다.

재귀라는 느낌이 오면 무조건 dfs 예상하고 그려보면서 어떤 변수를 전역변수로 둘 지, 아니면 인자로 전달할 지를 고민하는 것부터 해야겠다.

🚩 Solution

1. 접근법

TRY 1

스타트팀과 링크 팀의 중복을 고려하지 않음.

즉, N = 4일 때 스타트 = {0,1}과 스타트={2,3}이 동일한 결과를 도출한다는 것을 몰랐음.

TRY 2

STT는 무조건 0번째 사람을 끼고 시작한다고 설정해 두어 앞서 발생한 중복 문제를 피함.

(이건 간단한 경우의 수 문제인데, 0번을 낀 경우 == 0번을 안 낀 경우 == 전체 경우//2 이라는 것을 생각하면 됨.)

이렇게 하면 $(2nCn) /2 = (2n-1)C(n-1)$ 이므로 스타트 팀과 링크 팀을 중복하지 않게 잘 구할 수 있음.

위 그림을 참고해서 생각해 보자. 이때 chance는 스타트팀이 앞으로 선수를 몇번 더 뽑아야 하는 지를 알려 주는 변수다.

• chance가 0에 아직 도달하지 않은 경우: 어차피 스타트 팀(이하 stt)이 뽑는 대로 링크 팀(이하 link)에 선수가 채워지는 식이기 때문에, 스타트 팀만 선수를 고른다. 이때 선수를 하나씩 고르면 chance는 1씩 감소한다.
  • 이때 선수를 고르는 방식은, 전 선수 번호 +1 부터 N-chance 까지만 가능하도록 한다(중복 때문).
  • 즉 Ak를 k번째 선수 번호 후보의 집합이고 a(k-1)이 직전에 뽑은 선수의 번호라고 했을 때 Ak = {a(k-1)+1, ... N-chance} 이다(drawNew2Teams의 for문 참고).
  • for문이 종료되면, chance=지금chance-1 상태로 올라가서 다음 선수를 골라야 하므로 stt의 상태를 chance=지금chance-1 상태로 만들어준다.
    • 예) 원래 {0,1,5}이었으면 → chance==0에서 {0,1}로 롤백→ for문 끝나서 {0}으로 롤백.
      이는 {0,1,5} 다음에 {0,2,3}이 와야 하므로 이렇게 되는 것이다.
• chance가 0에 도달하는 경우: 선수를 더 이상 고르지 못한다.
  • link는 남은 선수들을 끌어 모아(findMissedNewBsLink) 지금까지 쌓아 온 각 팀의 역량의 차이를 구해 min_diff에 업데이트해 준다(updateMin 함수 참고).
  • 또 chance=1인 상태로 도로 올라가 다음 선수를 골라야 하므로(예: 0-1-2의 다음 케이스는 0-1-3) stt의 상태를 chance=1인 상태로 다시 만들어 주고 link는 아예 비워준다.
    • 이때 collections의 deque를 이용해서 삽입 삭제가 O(1)에 이뤄질 수 있도록 했다.
    • 예) 원래 {0,1,2}이었으면 → {0,1}로 롤백 후 for문에서 k++; → {0,1,3}
• 나머지는 코드가 보기 쉽게 정리되면 좋을 것 같다는 생각에서 함수를 따로 빼 준 것이고, 함수 이름과 동일한 기능을 한다.

2. 코드

import sys
from collections import deque

stt = deque(); link = deque()

skill = []; N = 0
min_diff = 2147483647

def main():
    global skill, N
    N = int(sys.stdin.readline())
    
    skill = list(map(lambda _: list(map(int, sys.stdin.readline().split())), range(N)))
    drawNew2Teams(0, N//2, 0)
    print(min_diff)

def drawNew2Teams(cur, chance, stt_skill):
    stt_skill += appendNew2Team(stt, cur); chance -= 1
    if chance == 0:
        link_skill = findMissedNewBsLink()
        updateMin(stt_skill, link_skill)
        stt.pop()
        while(len(link)!=0): link.pop()
    else:
        for k in range(cur+1, N-chance+1):
            drawNew2Teams(k, chance, stt_skill)
        stt.pop()
            
def findMissedNewBsLink():
    add_link_ab = 0
    if len(stt) != len(link):
        p = 0
        for i in range(len(stt)):
            add_link_ab += addNewBs2Link(p+1, stt[i])
            p = stt[i]
        if stt[i]!=N-1: add_link_ab += addNewBs2Link(p+1, N)
    return add_link_ab

def addNewBs2Link(front, end):
    if front +1 == end:
        return appendNew2Team(link, front)
    else:
        return sum(map(lambda i: appendNew2Team(link, i), range(front, end)))

def appendNew2Team(team, newcomer):
    plus_ability = calcAbility(team, newcomer)
    team.append(newcomer)
    return plus_ability

def calcAbility(team, newcomer):
    global skill
    plus_ability = 0
    for senior in team: 
        plus_ability += skill[newcomer][senior] + skill[senior][newcomer]
    return plus_ability

def updateMin(stt_ability, link_ability):
    global min_diff
    diff = abs(stt_ability - link_ability)
    min_diff = diff if diff<min_diff else min_diff

main()

3. 결과

시간 복잡도 분석

$O(((2NCN)/2)*N)$

즉 O(2^N) 인데 훨씬 적은,, 그런 느낌..