1535 : 안녕

• 실버2

시간제한	메모리제한	정답비율
2초	128MB	54%

input

1. n : 사람수

2. List[잃는 체력]

3. List[얻는 기쁨]

체력이 0이 되면 죽어서 아무 기쁨을 못 느낌으로 아예 안하는 경우를 빼면은 0 이 될 수 없다.

output : max(기쁨)

딱 봐도 dp 문제처럼 보임.

100이 되지 않는 선에서
그냥 다 흡수한다는 마인드?
근데 문제는 가성비가 안좋은 것에 대해서는 어떻게 처리를 해야할지?
그냥 f(n) = max(f(n-1), f(n-2))? 이런식으로 접근해야하나?

• N: 아이템의 수

• cost: 아이템의 무게 리스트

• value: 아이템의 가치 리스트

• dp: 동적 프로그래밍을 위한 2차원 배열. dp[i][j]는 i번째 아이템까지 고려하고, 배낭의 용량이 j일 때 얻을 수 있는 최대 가치를 저장합니다.

1. cost과 value 리스트의 맨 앞에 0을 추가합니다. 이렇게 0을 추가하는 이유는 아이템 인덱스와 용량을 1부터 시작하기 위함입니다. 따라서 실제 아이템 인덱스 1은 cost[1]과 value[1]이 됩니다.

2. 2차원 배열 dp를 생성하고 모든 원소를 0으로 초기화합니다. dp[i][j]는 i번째 아이템까지 고려하고, 배낭의 용량이 j일 때의 최대 가치를 나타냅니다.

3. 중첩된 반복문을 사용하여 dp 배열을 채웁니다. i를 1부터 N까지 순회하며 아이템을 하나씩 고려합니다. j를 1부터 100까지 순회하며 배낭의 용량을 고려합니다.

4. 각각의 (i, j)에 대해, 두 가지 경우를 비교합니다:

   1. 경우 1: cost[i] (i번째 아이템의 무게)가 j보다 작거나 같을 때, 아이템을 배낭에 넣을 수 있습니다. 따라서, dp[i][j]를 dp[i-1][j] (i-1번째 아이템을 고려할 때의 가치)와 dp[i-1][j-cost[i]] + value[i] (i번째 아이템을 넣었을 때의 총 가치) 중에서 더 큰 값으로 갱신합니다.

   2. 경우 2: cost[i] (i번째 아이템의 무게)가 j보다 크면, 해당 아이템을 배낭에 넣을 수 없으므로 dp[i][j]를 dp[i-1][j]로 갱신합니다.

5. 모든 아이템과 배낭 용량에 대해 계산을 마치면, dp[N][99]가 배낭의 최대 용량이 99일 때 얻을 수 있는 최대 가치를 나타내게 됩니다.

python

problem_num = 1535
import os, sys

path = os.getcwd() + f"\\txt\\{problem_num}" + ".txt"
sys.stdin = open(path, "r")
input = sys.stdin.readline

n = int(input())
cost = [0] + list(map(int, input().split()))
value = [0] + list(map(int, input().split()))

def happy(n, cost, value):
    dp = [[0 for _ in range(101)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, 101):
            if cost[i] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + value[i])
            else:
                dp[i][j] = dp[i - 1][j]

    return dp


dp = happy(n, cost, value)
print(dp[n][100 - 1])

135