[BOJ 3056] 007

문제

---

https://www.acmicpc.net/problem/3056

풀이

---

확률이 나와 당황스러울 수 있지만, 다른 비트필드에서의 DP 문제와 별반 다를 것이 없다.

미션을 이미 할당받은 지미 본드들의 정보와 현재까지의 성공 확률이 주어지면 부분 문제가 성립한다.

이 문제도 클레이 사격 게임처럼 최댓값을 구하고 있으므로 1차원 DP로 풀이 가능하다.

코드

---

import sys

n = int(sys.stdin.readline())
board = [list(map(lambda x: int(x) / 100, sys.stdin.readline().split())) for _ in range(n)]
dp = [0] * 2 ** n
dp[0] = (1, 0)

for mask in range(1, 2 ** n):
    res1 = 0
    use1 = 0
    for i in range(n):
        if mask & (1 << i):
            _, use2 = dp[mask ^ (1 << i)]
            if _:
                res2 = 0
                idx = -1
                for j in range(n):
                    if (not use2 & (1 << j)) and (res2 < board[i][j]):
                        res2 = board[i][j]
                        idx = j

                if idx != -1:
                    res2 *= dp[mask ^ (1 << i)][0]
                    use2 ^= (1 << idx)

                    if res1 < res2:
                        res1 = res2
                        use1 = use2

    dp[mask] = (res1, use1)

print(dp[-1][0] * 100)

이 문제는 Bottom-up 방식으로 풀어보았다.