[백준 1535번] 파이썬 - 안녕

백준 1535 - 안녕

시간 제한 2초, 메모리 제한 128MB

# 조건

• 세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다.
• 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.
• 세준이를 생각해준 사람은 총 N명이 있다.
• 사람의 번호는 1번부터 N번까지 있다.
• 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다.
  • 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.
• 세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다.
• 세준이의 체력은 100이고, 기쁨은 0이다.
  • 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다.
• 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄에 사람의 수 N(≤ 20)이 들어온다.
• 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 사람부터 순서대로 들어온다.
• 체력과 기쁨은 100보다 작거나 같은 자연수 또는 0이다.

출력

• 첫째 줄에 세준이가 얻을 수 있는 최대 기쁨을 출력한다.

# 접근 방법

• 냅색 알고리즘(배낭 문제)와 비슷하다.
• DP를 활용해서 풀어주었다.
• 잃어버리는 체력, 얻게되는 기쁨을 zip을 사용하여 tuple 형식으로 저장해준 후, 정렬해준다.
• 2중 for문을 돌리는데 바깥쪽은 N명의 사람 수만큼, 안 쪽은
  • 100 - 현재 인원을 만났을 때 잃어버리는 체력부터 1까지의 범위를 순회해준다.
  • 현재 잃어버릴 체력 + j가 100이 되는 순간부터는 현재 인원을 만날 수가 없기 때문이다.
• max를 이용하여 얻게 될 기쁨 + j에 기록된 값 vs j + 잃게 될 체력에 기록 된 값 중 큰 값을 dp[j+l]에 갱신해나가면 된다.

import sys
input = sys.stdin.readline

N = int(input())
values = list(map(tuple, zip(map(int, input().split()), map(int, input().split()))))

values.sort(key=lambda x: (x[0], x[-1]))

dp = [0] * 101
for i in range(N):
    l, g = values[i]
    for j in range(100-l, 0, -1):
        dp[j+l] = max(dp[j] + g, dp[j+l])
print(max(dp))