[백준] 1535. 안녕 (Python)

link 🔗 https://www.acmicpc.net/problem/1535

1535번: 안녕

 

✏️ DP 알고리즘

 

• 잘 풀리지 않아서 고전하다가, 잘 정리된 글(https://gsmesie692.tistory.com/113)을 발견하여 참고할 수 있었다.
• 2차원 배열로 문제를 해결하는데, 체력이 j보다 작으면 연락 불가능하므로 윗 배열의 값을 가져오고
• 체력이 j보다 크거나 같으면 새로운 값과 윗 배열의 값을 max 비교한다.
• 이때, j-power[i]는 앞서 연락을 취해 기쁨을 얻었을 경우 그 기쁨을 가져오는 것이다.

N = int(input())

power = [0]+list(map(int, input().split()))
joy = [0]+list(map(int, input().split()))

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

for i in range(1, N+1):
    for j in range(100):
        if power[i] > j: # j가 체력보다 작으면 연락 불가능
            DP[i][j] = DP[i-1][j] # 위의 값 가져오기
        else: # j가 체력보다 크거나 같으면 연락 가능
            DP[i][j] = max(DP[i-1][j-power[i]]+joy[i], DP[i-1][j]) # 새로운 값 vs 위의 값

print(DP[N][-1])