안녕하세요 코딩을 하고 있는 덕구입니다.
백준 14889 시작 및 링크입니다.
https://www.acmicpc.net/problem/14889
14889: 시작 및 연결
예시 2의 경우 팀을 (1, 3, 6), (2, 4, 5)로, 예시 3의 경우 (1, 2, 4, 5), (3, 6, 7, 8) 팀을 다음과 같이 나눕니다.
www.acmicpc.net
첫 번째 백준 14889 시작 및 링크 파이썬 정답 암호. 아래에 설명이 있습니다.
N = int(input())
team = (list(map(int, input().split())) for _ in range(N))
visited = (False for _ in range(N))
minimum = 1e9
def dfs(idx, depth):
global minimum
if depth == N//2:
start, link = 0, 0
for i in range(N):
for j in range(N):
if visited(i) and visited(j):
start += team(i)(j)
elif not visited(i) and not visited(j):
link += team(i)(j)
minimum = min(minimum, abs(start - link))
return
else:
for i in range(idx, N):
if not visited(i):
visited(i) = True
dfs(i+1, depth+1)
visited(i) = False
dfs(0, 0)
print(minimum)
문제 접근
당신이해야 할 일은 숫자를 시도하는 것입니다.
이때 중복되는 수식은 다시 계산하지 않음으로써 효율적으로 해결할 수 있습니다.
dfs를 통해 구현해 봅시다.
파이썬 코드 구현
인원수 N,
팀의 능력정보팀,
방문처리 확인을 위해 방문한 목록,
변수 minimum을 초기화하여 최소값을 저장합니다.
N = int(input())
team = (list(map(int, input().split())) for _ in range(N))
visited = (False for _ in range(N))
minimum = 1e9
모든 경우의 수를 확인하는 함수 dfs를 구현합니다.
먼저 팀이 구성되면(dfs의 깊이가 N//2인 경우) (출발팀은 방문팀, 연결팀은 비방문팀입니다.)
시작 및 연결 능력 값을 초기화합니다.
1. 모든 팀의 능력치 정보를 검색하여 선발팀일 경우(i,j 모두 방문 시) 선발 점수 상승
2. 모든 팀의 능력치 정보를 검색하여 링크팀일 경우 링크의 점수를 올린다(i와 j가 모두 방문하지 않은 경우).
두 값을 뺀 후 절대값과 최소값을 비교하여 값을 업데이트합니다.
def dfs(idx, depth):
global minimum
if depth == N//2:
start, link = 0, 0
for i in range(N):
for j in range(N):
if visited(i) and visited(j):
start += team(i)(j)
elif not visited(i) and not visited(j):
link += team(i)(j)
minimum = min(minimum, abs(start - link))
return
팀이 완료되지 않은 경우(else)
방문한 idx에서 N으로 팀이 방문하지 않은 경우
dfs를 방문하여 실행하십시오. (이 때 방문한 팀을 다시 확인하지 않도록 i + 1을 부여),
또한 모든 팀 구성이 종료되도록 dfs의 깊이를 +1합니다. (깊이 + 1)
for i in range(idx, N):
if not visited(i):
visited(i) = True
dfs(i+1, depth+1)
visited(i) = False
기능을 실행하고 인쇄하십시오.
dfs(0, 0)
print(minimum)
파이썬 백준 14889 시작 및 링크 이것이 최종 코드입니다.
N = int(input())
team = (list(map(int, input().split())) for _ in range(N))
visited = (False for _ in range(N))
minimum = 1e9
def dfs(idx, depth):
global minimum
if depth == N//2:
start, link = 0, 0
for i in range(N):
for j in range(N):
if visited(i) and visited(j):
start += team(i)(j)
elif not visited(i) and not visited(j):
link += team(i)(j)
minimum = min(minimum, abs(start - link))
return
else:
for i in range(idx, N):
if not visited(i):
visited(i) = True
dfs(i+1, depth+1)
visited(i) = False
dfs(0, 0)
print(minimum)
백준 14889호 시작 및 연결 자세한 설명과 파이썬 코드였습니다.
감사합니다