C. Potions #723 Div.2

https://codeforces.com/contest/1526/problem/C1
https://codeforces.com/contest/1526/problem/C2
시간 1초, 메모리 256MB

input :

• n (1≤n≤2000)
• a1 , a2, ... ,an (−109 ≤ ai ≤ 109)

output :

• Output a single integer, the maximum number of potions you can drink without your health becoming negative.
  건강을 나타내는 수치가 음수가 되지 않고 마실 수 있는 최대한의 포션 개수를 출력하시오.

조건 :

• Each potion will increase your health by ai when drunk. ai can be negative, meaning that potion will decrease will health.
  각 포션은 ai만큼 건강상태에 덧셈을 합니다. 음수도 존재할 수 있습니다.

• You start with 0 health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.
  건강상태는 0으로 시작하고 왼쪽에서 오른쪽으로 진행합니다. 각 위치에서 포션을 마실지 마시지 않을 지 선택 할 수 있습니다. 행동을 할 때에 언제나 건강상태는 양수여야 합니다.

dp를 이용해서 행 : 몇 개의 포션을 먹었는 지, 열 : 몇 번째 위치에 존재하는 지 해서 나타내면 되지 않을까 하는데 0의 경우에도 가능할 수 있기 때문에 추가로 생각해야 할 부분이 존재할 것 같다.

가장 시간 복잡도를 좋게 잡으려면 한 번의 반복문으로 마무리 해야 한다. 배열의 각 원소들을 확인 하면서 건강 상태의 합이 음수로 떨어진다면 현재까지 마신 포션 중 가장 작은 값(음수 포함)을 제거 함으로 먹은 포션 리스트를 유지한다.

이 갯수가 정답이 된다.

#solution from your_name_

import sys
from heapq import heappop, heappush

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
ans = []
cnt = 0

for item in data:
    cnt += item
    heappush(ans, item)

    if cnt < 0:
        temp = heappop(ans)
        cnt -= temp
print(len(ans))

2021.07.30
DP를 하는 경우를 다시 한 번 생각해보자.
i에는 현재 음료를 놓으려 했지만 j에 무엇이 와야 하는지를 몰랐다.
냅색처럼 각 음료를 먹을지 말지를 생각해야 할 거같다.

힌트를 통해 얻은 바 각 음료를 먹을 수 있을 때 현재까지 먹은 개수를 j에 저장하도록 하였다.
이를 통해 얻은 점화식은 [현재 음료 -1][먹은 개수 -1] + data[현재음료] 이렇게 계산을 하면 된다. 이 값이 음수가 아닌 값을 얻는 다면 이 값을 비교해서 저장한다.

즉, 이전 음료를 먹을 때 얻은 값에다가 현재 음료를 먹어서 건강상태를 업데이트 하는 것이다.
이게 안 된다면 그냥 이전 음료를 먹을 때 얻은 값을 그대로 가져온다.

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
dp = [[-float('inf')] * (n + 1) for i in range(n + 1)]
# 만들고 있는 dp의 형태가 [pos][drinks]를 기록하기 때문에
# 1행부터 시작을 하지만 점화식의 형태를 그 이전 행에 drinks - 1의 위치에 저장된 값에다가 현재의 음료 값을 더해서 얻기 때문에
# 우선적으로 0을 저장해 둬야 한다.
for i in range(n + 1):
    dp[i][0] = 0

for pos in range(1, n + 1):
    # 마실수 있는 음료의 수는 pos + 1까지 마실 수 있다.
    # pos의 경우 0에서 부터 시작하기 때문에 +1을 해줘야 한다.
    for drink in range(1, pos + 1):
        if dp[pos - 1][drink - 1] + data[pos - 1] >= 0:
            dp[pos][drink] = max(dp[pos - 1][drink - 1] + data[pos - 1], dp[pos - 1][drink])
        else:
            dp[pos][drink] = dp[pos - 1][drink]

ans = 0
for i in range(n + 1):
    if dp[n][i] >= 0:
        ans = i
print(ans)