[Python]1865. 동철이의 일 분배

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc

SW Expert Academy

---

 

이 문제는 일반적인 DFS로 풀면 시간초과가 발생한다.

적절한 시점에 Back Tracking 으로 가지치기를 하면(6번줄) 수행시간을 대폭 줄일 수 있다.

 

def norm(a):
    return int(a)/100
 
def dfs(depth, prob):
    global n, answer
    if prob <= answer:
        return
    if depth == n:
        answer = max(answer, prob)
        return
    for i in range(n):
        if not v[i]:
            v[i] = True
            dfs(depth + 1, prob * p[depth][i])
            v[i] = False
 
for t in range(int(input())):
    n = int(input())
    p = [list(map(norm, input().split())) for _ in range(n)]
    v = [False] * n
    answer = 0
    dfs(0, 100)
    print("#{} {:.6f}".format(t+1, answer))

 

<참고>

이 문제와 쌍둥이 문제가 있다.

7차시 5일차 - 배열 최소 합

https://www.swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWOVIc7KqfQDFAWg#

SW Expert Academy