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

1865. 동철이의 일 분배

---

문제)

 

동철이가 차린 전자회사에는 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%가 된다.

 

 

 

 

풀이)

소수점을 안쓰고 정수로만 해결하려고 했다가 조금 헤맸던 문제이다.

일반적인 DFS에 가지치기를 적용해주면 풀리는 문제이고,

여기에 dp를 적용할 수 있다고 하는데, 아직 내 역량에서는 하기 힘들었다.

아무래도 주말에 dp를 많이 풀어봐야 할 것 같다.

 

def recur(cur, total):
    global ans
    
    # 가지치기
    if total <= ans:
        return
 
    if cur == n:
        ans = max(ans, total)
        return
 
    for i in range(n):
        if visited[i]:
            continue
 
        visited[i] = 1
        recur(cur + 1, total * g[cur][i] * 0.01)
        visited[i] = 0
 
 
T = int(input())
for _ in range(T):
    n = int(input())
    g = [list(map(int, input().split())) for i in range(n)]
    visited = [0] * n
    ans = 0
    recur(0, 1)
    print(f"#{_ + 1} {ans * 100:.6f}")
 

 

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.