[SWEA] D4 1865 동철이의 일 분배 (Python)

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc&categoryId=AV5LuHfqDz8DFAXc&categoryType=CODE

문제

동철이가 차린 전자회사에는 N명의 직원이 있다.

그런데 어느 날 해야할 일이 N개가 생겼다.

동철이는 직원들에게 공평하게 일을 하나씩 배분하려고 한다.

직원들의 번호가 1부터 N까지 매겨져 있고, 해야 할 일에도 번호가 1부터 N까지 매겨져 있을 때, i번 직원이 j번 일을 하면 성공할 확률이 Pi, j이다.

여기서 우리는 동철이가 모든 일이 잘 풀리도록 도와주어야 한다.

직원들에게 해야 할 일을 하나씩 배분하는 방법은 여러 가지다.

우리는 여러 방법 중에서 생길 수 있는 “주어진 일이 모두 성공할 확률”의 최댓값을 구하는 프로그램을 작성해야 한다.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1 ≤ N ≤ 16)이 주어진다.

다음 N개의 줄의 i번째 줄에는 N개의 정수 Pi, 1, … , i, N(0 ≤ Pi, j ≤ 100)이 주어진다.

Pi, j는 i번 사람이 j번 일을 성공할 확률을 퍼센트 단위로 나타낸다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

모든 일을 성공할 확률이 최대화될 때의 확률을 퍼센트 단위로 소수점 아래 7번째 자리에서 반올림하여 6번째까지 출력한다.


[예제 풀이]

첫번째 직원이 첫번째 일을 담당하고, 두번째 직원이 두번째 일을 담당하고, 세번째 직원이 세번째 일을 담당할 때

모든 일을 성공할 확률이 최대가 되고 그 확률은 (0.13*0.7*1.0)*100 = 9.1%가 된다.

1 3 13 0 50 12 70 90 25 60 100

#1 9.100000

풀이

각각의 조합을 구해서 그 결과값을 비교하면 되겠다고 생각하였음. 사람과 일의 조합을 구하기 위해 DFS를 통해 가능한 조합을 모두 탐색하여 그 확률을 구함.

테스트 케이스가 100개나 되고 또 각 테스트 케이스의 데이터가 15개 이상인 것들이 많았기에 시간초과가 날 확률이 매우 높았고 실제로 시간초과가 났다...

시간초과를 잡기 위해서는 백트래킹을 통한 가지치기가 핵심이었는데 가지치기 조건을 잘 잡아줘야 했다.

나는 중간 결과값이 만약 현재 저장되어있는 최대값보다 작다면 앞으로도 가능성이 없다고 생각했다. 왜냐하면 곱해지는 값들이 모두 1보다 작기에 절대로 지금 상황에서 더 커질 수 없을테고 그렇다면 최대값보다 커질 확률은 0이기 때문이다. 그래서 result < max 라면 return  하라고 가지치기를 했건만 여전히 시간초과가 났는데.... result가 max랑 같아도 return 하라고 하니 시간초과 없이 pass가 되었다. 

 

코드

def johab(idx,end,result):
    global max_result
    if idx == end:
        if result > max_result:
            max_result = result
        return
    if result <= max_result: # 가지치기 중간까지의 결과값이 max보다 작으면 앞으로도 가능성 없음 // 곱하는 값들이 1보다 작기떄문에
        return 
    for i in range(N):
        if not visit[i]: # 방문 하지 않았다면 == 일이 선택되지 않았다면
            new_result = result * probability[idx][i] * 0.01 
            visit[i] = 1 
            johab(idx+1,end,new_result)
            visit[i] = 0 # return 되면서 방문 배열 초기화
        
T = int(input())
for t in range(T):
    N = int(input())
    probability = []
    for _ in range(N):
        probability.append(list(map(int,input().split())))
    visit =[0 for _ in range(N)] # 방문 배열 == 일
    max_result = -99999999
    johab(0,N,1)
    print("#{} {}".format(t+1,format(max_result*100,".6f")))