[BJ Q14889 with Python] 스타트와 링크: 시간단축, 백트래킹, 완전탐색 / Start and Link: Time Reduction, Backtracking, Brute Force

백준의 Wider93의 댓글을 참조하여 풀었습니다
I referred to Wider93's comments in BJ to solve this problem

이 문제는 파이썬으로 풀 때는 그냥 대충 백트래킹, 완전탐색 쓰면 안 풀린다. 경우의 수를 줄여주는 것이 필요하다.
You cannot solve this problem with Python unless you implemet certain time reduction methods. Some of the problem with BJ is that it is not optimized platform for Python.

Receving inputs

import sys
input = sys.stdin.readline
N = int(input())
stats = []
for _ in range(N):
    stats.append(list(map(int,input().split())))

Making variables to use. Define N_2 to reduce time

pick = [0 for x in range(N)]
sub = float('inf')
N_2 = N/2

Defining bruteforce function with backtracking method

def back(N2,s):
    global sub
    # ending condition
    if N2 == N_2:
        result = 0 
        y0, y1 = [], []
        # sorting the values in pick in advance so that it can iterate less
        for yi,yv in enumerate(pick):
            if yv == 1:
                y1.append(yi)
            else:
                y0.append(yi)
        for xi,xv in enumerate(pick):
            if xv == 1:
                for yi in y1:
                    result += stats[xi][yi]
            else:
                for yi in y0:
                    result -= stats[xi][yi]
        sub = min(sub, abs(result))
        return

Pick from player+1 to prevent redundancy

 	for player in range(s,len(pick)):
        if pick[player] == 0:
            pick[player]=1
            back(N2+1,player+1)
            pick[player]=0

좋은 웹페이지 즐겨찾기