동철이의 일 분배 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 1865

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

동철이가 차린 전자회사에는 N명의 직원이 있다. 그런데 어느 날 해야할 일이 N개가 생겼다. 동철이는 직원들에게 공평하게 일을 하나씩 배분하려고 한다. 직원들의 번호가 1부터 N까지 매겨져 있고, 해야 할 일에도 번호가 1부터 N까지 매겨져 있을 때, i번 직원이 j번 일을 하면 성공할 확률이 Pi, j이다. 여기서 우리는 동철이가 모든 일이 잘 풀리도록 도와주어야 한다. 직원들에게 해야 할 일을 하나씩 배분하는 방법은 여러 가지다. 우리는 여러 방법 중에서 생길 수 있는 “주어진 일이 모두 성공할 확률”의 최댓값을 구하는 프로그램을 작성해야 한다.

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1 ≤ N ≤ 16)이 주어진다. 다음 N개의 줄의 i번째 줄에는 N개의 정수 Pi, 1, … , i, N(0 ≤ P(i, j) ≤ 100)이 주어진다. P(i, j)는 i번 사람이 j번 일을 성공할 확률을 퍼센트 단위로 나타낸다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 모든 일을 성공할 확률이 최대화될 때의 확률을 퍼센트 단위로 소수점 아래 7번째 자리에서 반올림하여 6번째까지 출력한다.

예시

입력	출력
1 3 13 0 50 12 70 90 25 60 100	#1 9.100000

---

2. 문제풀이

확률을 구하는 문제인데 N이 16까지 있기때문에 단순한 dfs만을 이용하면 터질것이다. 따라서 확률을 이용한 가지치기가 필요해 보인다. 일반적인 dfs처럼 돌리는데 재귀를 할때 지금값이 현재 가지고있는 최대확률보다 낮아진다면 리턴하도록 설정했다. 만약 내 최대 확률이 10%인데 현재 확률이 9%라면 뒤에 성공확률이 계속 100퍼라고 해도 최대 9%이기 때문에 뒤에 내용을 더 이상 보지 않아도 된다.

---

3. 소스코드

#D4 1865 동철이의 일 분배
#N = 일의 개수 1 <= N <= 16
#각줄은 직원의 성공 확률
 
def bfs(idx, answer = 100):
    global max_value
    #값이 계산한 이전값보다 작다면 리턴
    if answer <= max_value: return
    #위에서 걸러지므로 여기까지 왔다면 그냥 값을 넣는다.
    if idx >= N:
        max_value = answer
        return
    #조합을 구해서 bfs하기
    for i in range(N):
        if use_check[i]:
            use_check[i] = False
            bfs(idx+1, answer * (success_list[idx][i]) )
            use_check[i] = True
 
 
T = int(input())
for t in range(1, T+1):
    N = int(input())
    #람다식을 이용하여 넣을때부터 100으로 나누어 사용
    success_list = [list(map(lambda x : int(x)/100, input().split())) for _ in range(N)]
    use_check = [True for _ in range(N)]
    max_value = 0
    bfs(0)
    #6자리수로 제한하여 출력
    print('#{} {:6f}'.format(t, max_value))