[SWEA] 5209. [파이썬 S/W 문제해결 구현] 5일차 - 최소 생산 비용 [D3]
📚 문제
📖 풀이
중복없는 순열 문제이다. 1, 2, 3, ... 순서대로 A C B ... 처럼 중복되지 않게 고르면 된다.
그냥 재귀로 백트래킹 없이 해결하면 O(n!)의 시간복잡도로 n이 15까지 이니 15!이다.
1307674368000로 1조를 넘어가는 큰 경우의 수가 나오게 되니, 백트래킹으로 줄여줘야 한다.
cur을 끝까지 돌며 현재까지 구한 최소 생산 비용보다 현재 구하고 있는 생산 비용이 더 크거나 같으면 절대 답이 될 수 없으므로 가지치기 해준다.
📒 코드
def recur(cur, total): # 중복 없는 순열
global min_total
if total > min_total: # 가지치기
return
if cur == n:
min_total = min(min_total, total)
return
for i in range(n):
if visited[i] == 1:
continue
visited[i] = 1
recur(cur + 1, total + arr[cur][i])
visited[i] = 0
t = int(input())
for tc in range(1, t + 1):
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [0 for _ in range(n)] # 방문 표시
min_total = 100 * n
recur(0, 0)
print(f'#{tc} {min_total}')
🔍 결과
Author And Source
이 문제에 관하여([SWEA] 5209. [파이썬 S/W 문제해결 구현] 5일차 - 최소 생산 비용 [D3]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/SWEA-5209.-파이썬-SW-문제해결-구현-5일차-최소-생산-비용-D3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)