Enochkon's blog

문제

1535번: 안녕

코드

n = int(input())
lost = list(map(int,input().split()))
happy = list(map(int,input().split()))
hp = 100
pleasure = 0
arr= [[0 for _ in range(101)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,101):
        if(j-lost[i-1]>0):
            arr[i][j] = max(arr[i-1][j], arr[i-1][j-lost[i-1]] + happy[i-1])
        else:
            arr[i][j]=arr[i-1][j]

print(arr[n][100])

풀이

• 간단한 dp 문제

1. 사용 체력과 얻는 기쁨을 배열로 받아준다.
2. dp 배열을 arr[i][j] (i : 체력, j : 사람 순서)로 작성해준다.
3. 이중 반복문을 사용해서 체력이 0 이하가 되면 바로 인사를 하지 않고 바로 전 사람까지의 기쁨 값을 가져온다 (i-1)
   1. 체력이 0이하로 떨어지지 않으면 바로전까지의 기쁨 값과, 인사를 했을 때 추가되는 값중 큰 값을 새로 입력해준다.
4. 전부 순회한 후 제일 마지막 최대값을 출력해준다.