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

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 재귀로 순열을 구현해서 경우의 수를 찾아주고 확률을 곱해준다.
2. success리스트에 들어있는 확률은 전부 1이하 이므로 total이 max_success보다 작다면, 더 이상 커질 수 없다고 판단하여 리턴시켜서 가지치를 해줬다.

 

📌 코드

import sys
sys.stdin = open('input.txt')

def permutation(total):
    global staff, max_success

    if total <= max_success:
        return

    if len(staff) == N:
        max_success = max(max_success, total)
        return
    else:
        for i in range(N):
            if i not in staff:
                staff.append(i)
                permutation(total * (success[len(staff)-1][staff[-1]] / 100))
                staff.pop()


T = int(input())

for t in range(1, T+1):
    N = int(input())
    success = [list(map(int, input().split())) for _ in range(N)]
    staff = []

    max_success = 0
    permutation(1)

    print('#{} {:0.6f}'.format(t, round(max_success*100, 6)))