[백준] 1535 안녕

문제

• 세준이를 생각해준 사람이 1~N번까지 있을 때, i번 사람에게 인사하면 L[i] 만큼의 체력을 잃고 J[i]만큼의 기쁨을 얻는다.
• 100의 체력 내에서 느낄 수 있는 최대한의 기쁨은?
• 1 <= N <= 20
  
  
  

 

풀이

• 알고리즘 : 배낭 문제 (0-1 Knapsack)
  • n 번째 물건을 배낭에 넣을 수 없다.
    -> n-1 개의 물건들을 갖고 구한 전 단계의 값을 그대로 가져온다.
  • n 번째 물건을 배낭에 넣을 수 있다.
    -> max( 물건 안넣을 때의 값, 물건 넣었을 때의 값)
    -> max( n-1 개의 물건들을 갖고 구한 전 단계의 값, n 번째 물건만큼의 무게를 비웠을 때의 값 + n 번째 물건)
• dp[N][life] : N명까지의 사람을 만났을 때, life 만큼의 체력으로 얻을 수 있는 최대 기쁨
  
  • 남은 체력을 1~100까지라고 생각할 때, 
  • 만약 현재 남은 체력 j가 소모될 체력 life보다 크다면 (현재 사람 안만나기 vs 만나기) 중 더 기쁨이 큰 경우를 선택하고
    작다면 만날 수 없으므로 이전 사람을 만났을 때의 값을 그대로 가져온다.

 

N = int(input())
L = list(map(int, input().split()))
J = list(map(int, input().split()))

dp = [[0]*101 for _ in range(N+1)]

for i in range(1, N+1) :
    life, joy = L[i-1], J[i-1]

    for j in range(1, 101) :        # 체력이 1~100일 경우
        if life <= j :              # 남은 체력으로 현재 사람 만날 수 있다면
            # 현재 사람 안만나기 vs 만나기 중 더 기쁨이 큰 경우 선택 
            dp[i][j] = max(dp[i-1][j], joy + dp[i-1][j-life])
        else :                      # 남은 체력으로는 못만나는 경우
            dp[i][j] = dp[i-1][j]

print(dp[N][100])

 

References

• 백준 DP