[ SW Expert Academy / 1865] 동철이의 일 분배

1. 문제 이해

“주어진 일이 모두 성공할 확률”의 최댓값을 구하기 위해선 일 분배를 어떻게 해야 할지?

입력값:
테스트 케이스 T
직원 수 , 일 수 N
i 직원이 j 일을 맡았을 때 성공률 (N 줄에 걸쳐, ' '으로 나누어져 있음)

유의해야 할 점:
성공률이 0인 것도 있음

출력 값:
#테스트 케이스, 모두 성공할 확률의 최댓값 ( 소수 일곱째 자리에서 반올림)

 

2. 문제 풀이 법

사용한 방법: DFS 순열

1. 각 일에 대한 순서는 답에 영향을 주지 않는다.
2. 성공률은 <1 이므로 곱할수록 작아진다.

인자 : 일꾼 번호, 현재까지 성공률 

1. 일꾼 번호 = 사람 수 면 일이 다 배정되었다는 뜻이므로 return

2. 아닌 경우 일꾼 n에 대해 1~n까지 일을 할당한다.
 i) visited [일] = 0이고 성공률이 0이 아닌 경우
        일을 할당해준다 visited 체크, 재귀 함수(일꾼 번호 +1, 현재까지 성공률 * 이일을 n이 했을 때 성공률 / 100)
        
        visited 체크 해제 ( n이 이 일을 안 맡고 다른 일을 맡을 수도 있으니까) 

 

3. 어려웠던 점

순열을 dfs로 만들 수 있다는 것을 처음 알았다.
기본적인 공식을 알아야 응용할 수 있는데 차근히 정리해 보아야겠다.

1. 정답

T = int(input())
 
def perm(n,temp_success):
    global success
    if N == n:
        success = max(success,temp_success)
        return
 
    if temp_success <= success:
        return
 
    for i in range(N):
        if not visited[i] and table[n][i]:
            visited[i] = 1
            perm(n+1,temp_success*table[n][i]/100)
            visited[i] = 0
 
 
for tc in range(1,T+1):
    N = int(input()) #일의 수, 사람의 수
    table = [list(map(int,input().split()))for _ in range(N)]
    success = 0  # 모든 일이 성공할 확률
    visited = [0 for _ in range(N)]
    result = [0 for _ in range(N)]
 
    # print(table)
    perm(0,1)
 
    print( '#{} {}'.format(tc,'%.6f' % (success*100)))

2. 정답이 나오지만 시간이 엄청 많이 걸리는 코드

 

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

T = int(input())

def perm(n,k):
    global success
    if k == n:
        temp_success = 1
        for i in range(N):
            temp_success *= table[wp[i]-1][i]
            if temp_success <= success:
                return
        success = temp_success
        return
    else:
        for i in range(k,N):
            wp[k], wp[i] = wp[i], wp[k]
            perm(n,k+1)
            wp[k], wp[i] = wp[i], wp[k]

for tc in range(1,T+1):
    N = int(input()) #일의 수, 사람의 수
    table = [list(map(int,input().split()))for _ in range(N)]
    success = 0  # 모든 일이 성공할 확률
    wp = [_ for _ in range(1, N + 1)]

    for i in range(N):
        for j in range(N):
            table[i][j] *= 0.01

    perm(N,0)

    print( '#{} {}'.format(tc,"%0.6f" % round(success*100,7)))

 

 

 

4. 배운 점

소수 n번째에서 반올림하는 법
round(수, n)

소수 n번째까지 표기하는 법
"%0.6f" % 수

 

혹시 더 좋은 풀이나 조언이 있다면 댓글 달아주세요.