[백준/11394] 최적의 능력 구성 (Python)

Problem : https://www.acmicpc.net/problem/11394

11394번: 최적의 능력 구성

 

Difficulty : Gold 1

 

Status : Solved(pypy3)

 

Time : 00:11:43

 

---

 

문제 설명

 

 

경근이는 요즘 여러 능력을 가지고 몬스터들과 싸우는 웹게임을 열심히 하고 있다. 경근이는 지금 N개의 공격 능력을 가지고 있다. 경근이는 능력들을 편하게 관리하고자 각 능력에 1 이상 N 이하의 자연수 번호를 붙였다.

i번 능력에는 그 능력이 발동될 확률 pi와 상대에게 입히는 피해량 di가 책정되어 있다. 따라서 경근이가 i번 능력에 발동 명령을 내리면, pi의 확률로 능력이 발동되어 상대에게 di만큼의 피해를 입히고, (1 - pi)의 확률로 능력이 발동되지 않아 아무 일도 일어나지 않는다.

열심히 게임을 한 결과, 경근이는 드디어 게임 내에서 모든 능력을 자유롭게 장착하고 해제할 수 있게 되었다! 이제 경근이는 상대가 입을 피해량의 기댓값이 최대가 되도록 하기 위해 어떤 능력들을 장착해야 할지를 알고 싶다. 경근이가 어떤 능력(들)을 장착한 채로 상대방을 공격할 기회를 얻었다면, 아래 과정이 일어난다:

 

• 하나의 능력만 장착했을 때: 해당 능력에 발동 명령을 내린 후, 그 결과와 상관 없이 공격 기회를 잃는다.
• 두 개 이상의 능력을 장착했을 때: 가지고 있는 모든 능력들 중 하나를 임의로 고른다. 모든 능력을 고를 확률은 서로 같다. 고른 능력에 발동 명령을 내린다. 만약 이 능력이 발동되었다면, 공격 기회를 잃고 과정이 끝난다. 하지만 이 능력이 발동되지 않았다면, 아직 발동 명령을 내려 보지 않은 능력들 중 하나를 동일한 확률로 무작위하게 고른 후, 다시 발동 명령을 내린다. 만약 능력이 발동되었다면 공격 기회를 잃은 후 과정을 끝내고, 발동되지 않았다면 같은 과정을 더 이상 발동 명령을 내려 보지 않은 능력이 없을 때까지 반복한다. 모든 능력에 발동 명령을 내렸음에도 발동된 능력이 하나도 없으면 공격 기회를 잃는다.

현재 경근이가 가지고 있는 N개의 능력이 발동될 확률과 상대에게 입히는 피해량이 주어질 때, 한 번의 공격 기회에서 피해량의 기댓값이 최대가 되도록 하기 위해 장착해야 할 능력의 집합을 구하는 프로그램을 작성하라.

 

 

입력 및 출력

 

입력

첫 번째 줄에 자연수 N (1 ≤ N ≤ 20)이 주어진다. 다음 N개의 줄에는 능력들의 정보가 주어진다. 이 중 i (1 ≤ i ≤ N)번째 줄에는 i번 능력이 발동될 확률과 상대에게 입히는 피해량을 의미하는 두 정수 pi, di (1 ≤ pi , di ≤ 100)이 공백을 사이로 두고 주어진다. 이는 i번 능력은 pi% ( = pi / 100)의 확률로 발동하는 능력이며 상대에게 di만큼의 피해를 입힌다는 의미이다.

 

출력

가지고 있는 능력들을 적절히 장착하여 얻을 수 있는 피해량의 기댓값의 최댓값을 출력한다. 정답과의 절대/상대 오차가 10-8 이하이면 올바른 답안으로 처리된다.

 

입력 예시

 

2
100 1
10 20

 

출력 예시

 

2
100 1
10 20

 

 

---

 

풀이

 

N이 최대 20이므로 비트마스킹을 이용해봄직하다.

 

총 n개 능력을 조합하는 경우의 기댓값을 En라고 두자.

• n = 1일 경우 : 기댓값은 (확률 * 피해량)이 된다.
• n > 1일 경우 : n+1인 경우를 생각하자. n개에 포함되지 않은 새로운 기댓값이 주어진다.
  • 새로운 기댓값이 발동될 경우 : E1
  • 새로운 기댓값이 발동되지 않을 경우 : (발동되지 않을 확률) * En
  • 즉 총 기댓값은 E(n+1) = sum(E1 + (1-p)En) / (n+1)으로 재귀적으로 구성된다.

풀이 코드

N = int(input())
dp = [0]*(1<<N)
skills = [[*map(int, input().split())] for _ in range(N)]

for i in range(N) :
  dp[1<<i] = skills[i][0]/100*skills[i][1]
for i in range(1, 1<<N) :
  dp[i] /= bin(i).count('1')
  for j in range(N) :
    if i & (1 << j) :
      continue
    dp[i|(1<<j)] += dp[1<<j] + (100-skills[j][0])/100*dp[i]
print(max(dp))

풀이 완료!