SWEA D4 Python 1865: 동철이의 일 분배
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
# 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자리)
시간 더 줄이는 방법 난 몰라
728x90
'Algorithm > SWEA' 카테고리의 다른 글
| 1966 숫자를 정렬하자 (0) | 2022.02.10 |
|---|---|
| 2007 패턴 마디의 길이 (0) | 2022.02.10 |