파이썬으로 풀어보는 백준 14889번: 스타트와 링크

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

내 풀이:

N = int(input())
match = [list(map(int, input().split())) for _ in range(N)]
team_set = {i for i in range(N)}
total = 0
for _ in range(N):
    total += sum(match[_])
answer = 1000
 
def score(team):
    result = 0
    result2 = 0
    for i in team:
        for j in team:
            result += match[i][j]
    team2 = list(team_set - set(team))
    for i in team2:
        for j in team2:
            result2 += match[i][j]
    return abs(result - result2)
 
 
def make_teams(num, team):
    global answer
    if num == N//2:
        if answer > score(team):
            answer = score(team)
        else:
            return
 
    if num == 0:
        for _ in range(0, N//2):
            team.append(_)
            make_teams(num+1, team)
            team.remove(_)
 
    else:
        for i in range(max(team)+1, N):
            team.append(i)
            make_teams(num+1, team)
            team.remove(i)
 
make_teams(0, [])
print(answer)

Python3, 3960ms

4명의 선수가 있다고 가정할 때, 내 코드는 1번과 2번을 스타트 팀으로 묶어 감소값을 뽑아도 나중에 3,4번 선수를 스타트 팀으로 선출하면서 결과적으로 한번의 결과를 두 번 계산하는 불필요한 과정이 포함되어 있다. 이 외에도 소요 시간이 3960ms나 걸리는 것을 보아 팀을 만들 때 알고리즘도 최적화가 필요하다는 것을 알 수 있다.

 

N = int(input())
match = [list(map(int, input().split())) for _ in range(N)]
team_set = {i for i in range(N)}
total = 0
for _ in range(N):
    total += sum(match[_])
answer = 1000
 
def score(team):
    result = 0
    result2 = 0
    for i in team:
        for j in team:
            result += match[i][j]
    team2 = list(team_set - set(team))
    for i in team2:
        for j in team2:
            result2 += match[i][j]
    return abs(result - result2)
 
def make_teams(num, team):
    global answer
    if num == N//2:
        if answer > score(team):
            answer = score(team)
        else:
            return
 
    for i in range(max(team)+1, N):
        team.append(i)
        make_teams(num+1, team)
        team.remove(i)
 
make_teams(1, [0])
print(answer)

Python3, 1892ms

앞서 언급한 중복을 막기 위해서 스타트 팀에는 반드시 1번 선수가 포함되도록 코드를 수정했다. 1번 선수가 포함된 팀과 1번 선수가 없는 팀으로 나누면 정확히 절반의 경우의 수로 줄일 수 있다. 결과를 확인해도 3960ms에서 딱 절반 수준의 시간으로 감소시킬 수 있었다.

 

 

N = int(input())
match = [list(map(int, input().split())) for _ in range(N)]
team_set = {i for i in range(N)}
answer = 1000
 
 
def score(team):
    result = 0
    result2 = 0
    for i in team:
        for j in team:
            result += match[i][j]
    team2 = list(team_set - set(team))
    for i in team2:
        for j in team2:
            result2 += match[i][j]
    return abs(result - result2)
 
 
def make_teams(num, team):
    global answer
    if num == N // 2:
        if answer > score(team):
            answer = score(team)
        return
 
    for i in range(max(team) + 1, N):
        team.append(i)
        make_teams(num + 1, team)
       team.pop(0)
 
 
make_teams(1, [0])
print(answer)

Python3, 1920ms

필요없는 부분 삭제 및 수정. 서버의 상태가 전보다 별로인지 시간은 오히려 증가.