[SWEA][D4][#01865] 동철이의 일 분배

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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

예제

입력

1
3
13 0 50
12 70 90
25 60 100

출력

#1 9.100000

My Sol

def foo(i, P):
    global maxP

    if i==N:
        maxP = maxP if maxP > P else P
        return

    if P < maxP:
        return

    for j in range(N):
        if visited[j]: continue
        if not mat[i][j]: continue
        visited[j] = 1
        foo(i+1, P*mat[i][j]/100)
        visited[j] = 0


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    mat = [list(map(int, input().split())) for _ in range(N)]
    visited = [0]*N
    maxP = 0
    foo(0, 1)
    print(f'#{tc} {maxP * 100:.6f}')

백트래킹을 이용해서 풀었던 문제이다. 최대 확률인 maxP보다 인자로 넘기는 P가 작아진다면 더 이상의 조회는 무의미하므로 이후는 제거해주며 가지치기한다.

결과

PASS

모범답안

T = int(input())
for tc in range(1, T + 1):
    N = int(input())
 
    arr = [list(map(int, input().split())) for _ in range(N)]
    memo = [[0] * (1 << N) for _ in range(N)]
 
 
    for i in range(N):
        memo[0][1 << i] = arr[0][i]
 
    for r in range(N):
        for c in range(N):
            for bit in range(1 << N):
                if memo[r][bit] == 0 or bit & (1 << c): continue
 
                if memo[r + 1][bit | (1 << c)]:
                    memo[r + 1][bit | (1 << c)] = max(memo[r + 1][bit | (1 << c)], memo[r][bit] * arr[r + 1][c] / 100)
 
                else:
                    memo[r + 1][bit | (1 << c)] = memo[r][bit] * arr[r + 1][c] / 100
 
    ans = memo[N - 1][(1 << N) - 1]
    print(f'#{tc} {ans:.6f}')

반에서 가장 잘하시는 분의 코드이다. memoization과 반복을 통한 DP를 사용하셨다. visited 같은 경우 bit와 bit shift를 이용해 깔끔하게 표시하셨고, 2차원 memoization을 설정하여 작성하였다. 내 코드의 절반정도의 연산시간으로 반 전체의 효율을 훨씬 윗도는 연산시간을 보여주셨다.