[백준/26218] 생산 시스템 관리 (Python)

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

26218번: 생산 시스템 관리

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:17:43

 

---

 

문제 설명

 

 

겨울 숲의 나라에는 N종류의 작업으로 이루어진 생산 시스템이 있다. 이 생산 시스템에서 모든 작업이 올바르게 작동하게 하려고 한다.

작업 i는 기계 i를 가동함으로써 이루어진다. 기계 i를 1대 갖췄을 때 작업 i가 올바르게 작동할 확률은 pi / 100이며, 여기에 기계 i를 추가로 한 대 더 구매할 때마다 작업 i가 올바르게 작동할 확률이 ai / 100 늘어난다. 단, 기계 i를 아무리 많이 구매해도 작업 i가 올바르게 작동할 확률은 1을 넘을 수 없다.

예를 들면, 작업 1과 작업 2가 존재하면서 p1 = 40, p2 = 60, a1 = 15, a2 = 10인 경우, 기계 1과 기계 2를 각각 한 대씩 있을 때 모든 작업이 올바르게 작동할 확률 P는 0.4 * 0.6 = 0.24가 된다. 하지만 기계 1과 기계 2를 각각 2대, 1대 추가로 구매해서 총 각각 3대, 2대를 갖춘다면 P는 (0.4 + 0.15 * 2) * (0.6 + 0.1 * 1) = 0.49로 개선된다. 기계 i의 가격이 각각 ci일 때, 총 비용을 B 이하로 사용해서 P를 최대화시키는 방법은 무엇인가?

초기 상태에는 모든 종류의 기계가 한 대씩 존재한다.

 

 

입력 및 출력

 

입력

 

첫 줄에 작업들의 종류의 수를 의미하는 정수 N (1 <= N <= 9) 과 비용 B (0 <= B <= 30,000)가 주어진다.

다음 N개의 줄에 걸쳐 기계 i에 대한 pi, ai, ci가 공백으로 구분되어 정수로 주어진다. (1 <= pi, ai <= 99, 1 <= ci <= 30,000)

 

출력

 

첫 번째 줄에 총 비용을 B 이하로 사용했을 때 P의 가능한 최댓값에 10^{2N}을 곱한 값을 출력한다. 이 값은 항상 정수이다.

두 번째 줄에 그 때 추가로 구매해야 하는 기계 i의 대수를 차례로 공백으로 구분하여 출력한다.

가능한 방법이 여럿일 경우 그 중 아무거나 출력한다.

 

입력 예시

 

2 450
40 15 200
60 10 150

 

출력 예시

 

4200
2 0

 

 

 

---

 

풀이

 

배낭 문제의 확장판. 추가 금액이 0원(pi) 에서 확률이 100이 될 순간까지(pi + ai * n >= 100)의 값 n * ci원까지로 존재할 수 있으므로, 이들을 고려해서 DP를 업데이트한다. 

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = float('inf')

N, B = map(int, input().split())
machines = []

for i in range(N) :
  p, a, b = map(int, input().split())
  c = 0
  tmp = []
  while True :
    if p > 100 :
      tmp.append((100, c))
      break
    tmp.append((p, c))
    p += a
    c += b
  machines.append(tmp)

dp = [[(0, 0, 0)]*(B+1) for _ in range(N+1)]
dp[0][0] = (1, 0, 0)

for i in range(N) :
  for j in range(B+1) :
    if dp[i][j] == (0, 0, 0) :
      continue
    for idx, (p, c) in enumerate(machines[i]) :
      if j+c > B :
        break
      if dp[i+1][j+c][0] < dp[i][j][0] * p :
        dp[i+1][j+c] = (dp[i][j][0] * p, idx, j)

idx = dp[-1].index(max(dp[-1]))
print(dp[-1][idx][0])
result = []
for i in range(N, 0, -1) :
  result.append(dp[i][idx][1])
  idx = dp[i][idx][2]
print(*reversed(result))

풀이 완료!