[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
Author And Source
이 문제에 관하여([BJ Q14889 with Python] 스타트와 링크: 시간단축, 백트래킹, 완전탐색 / Start and Link: Time Reduction, Backtracking, Brute Force), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyeong/BJ-Q14889-with-Python-스타트와-링크-시간단축-백트래킹-완전탐색-Start-and-Link-Time-Reduction-Backtracking-Brute-Force저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)