[swjungle 2기] 백준 1535 안녕

1535번: 안녕

- 냅색문제를 연습하고 싶어 몇가지 풀어보았습니다.

- 전형적인 냅색문제지만 세준이의 HP가 0이되면 세준이가 인사를 하다 죽어버리므로 hp100일때 기준은 제외해 버립니다. (포함시키면 55가 출력됩니다)

- hp가 1기준일때 인사를 할 수있는 가능성부터 99일때 가능성을 구하여 최대 행복도를 구합니다.

import sys

N = int(sys.stdin.readline())
hp = [0] + list(map(int, sys.stdin.readline().strip().split()))
happy = [0] + list(map(int, sys.stdin.readline().strip().split()))

matrix = [[0] * 100 for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, 100):
        hpD = hp[i]
        happyG = happy[i]
        if j < hpD:
            matrix[i][j] = matrix[i - 1][j]
        else:
            matrix[i][j] = max(happyG + matrix[i - 1]
                               [j - hpD], matrix[i - 1][j])

print(matrix[-1][-1])