1865 동철이의 일 분배

SWEA D4 Python 1865: 동철이의 일 분배

SW Expert Academy

# 2022-03-31

def success(i, N, p):	# DFS (p = 각 단계마다 구해지는 확률)
    global ans
    if i == N:
        if p * 100 > ans:
            ans = round(p * 100, 6)
    elif p * 100 <= ans:	# 확률이 더 낮아지는 순간 break (<= 말고 < 쓰면 시간초과)
        return

    else:	# 열 값 (각 직원이 맡을 일의 번호) 정할 순열 만듦
        for j in range(i, N):
            P[i], P[j] = P[j], P[i]
            success(i+1, N, p * (W[i][P[i]]) / 100)
            P[j], P[i] = P[i], P[j]



T = int(input())
for tc in range(1, T+1):
    N = int(input())
    W = [list(map(int, input().split())) for _ in range(N)]
    P = [x for x in range(N)]
    ans = 0

    success(0, N, 1)
    print(f'#{tc}', '{:.6f}'.format(ans))	# 문제 출력 형식(소수점 이하 6자리)

 

시간 더 줄이는 방법 난 몰라