[BOJ][Python]1535번 풀이

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

1535번: 안녕

n = int(input())
p = [0]
h = [0]
p.extend(list(map(int, input().split())))
h.extend(list(map(int, input().split())))
t = [[0 for _ in range(101)] for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(101):
        if j<p[i]:
            t[i][j] = t[i-1][j]
        else:
            t[i][j] = max(h[i]+t[i-1][j-p[i]], t[i-1][j])
print(t[n][99])

어제 말씀드렸던 대로 배낭 문제로 찾아왔습니다. 문제는 배낭 어쩌구가 아니지만 알고리즘이 같으니까요. 아직 딱 보자마자 바로 슉슉 해버릴 정도로 익숙하진 않은데 일단 재미는 있었습니다. 몇 문제 더 해보고 좀 더 난이도 높은 문제도 도전하다보면 자신감이 생길 것 같네요.

 

해당 문제에서 놓치면 안되는 부분은 체력을 100을 다 쓰면 안된다는 점입니다. 따라서 마지막에 답을 출력할 때는 99일 때의 최대값을 출력하면 되겠네요. 저는 하다가 그 부분을 깜빡하는 바람에 데이터를 하나하나 다 뜯어보는 시간을 거쳤습니다. 여러분은 항상 조건 확인하는거 잊지마세요.