안녕
면접 대비시간 제한2초메모리 제한128 MB
최대 20명의 사람에 대해 건강 손실과 기쁨 값이 주어질 때, 총 건강 손실이 100 미만이 되도록 선택해 기쁨의 합을 최대화합니다.
- 난이도
쉬움10점 중 3점
- 유형
- 동적 계획법
- 정답자
- 아직 제출이 없습니다
문제
세준이는 수술을 받은 뒤 병원에 오랫동안 입원해 있었다. 이제 세준이는 입원해 있는 동안 자신을 걱정해 준 사람들에게 감사 인사를 하려 한다.
사람은 총 N명이고, 번호는 1번부터 N번까지이다. 세준이가 i번 사람에게 인사하면 체력을 L[i]만큼 잃고 기쁨을 J[i]만큼 얻는다. 각 사람에게는 최대 한 번만 인사할 수 있다.
세준이의 처음 체력은 100이고 처음 기쁨은 0이다. 인사를 마친 뒤 체력이 0 이하가 되면 아무 기쁨도 느끼지 못한다. 체력이 양수로 남도록 인사할 사람을 골랐을 때, 얻을 수 있는 최대 기쁨을 구하시오.
입력
첫째 줄에 사람의 수 N이 주어진다. (N <= 20)
둘째 줄에는 1번 사람부터 N번 사람까지, 인사할 때 잃는 체력 L[i]가 순서대로 주어진다.
셋째 줄에는 1번 사람부터 N번 사람까지, 인사할 때 얻는 기쁨 J[i]가 순서대로 주어진다.
모든 체력과 기쁨 값은 0 이상 100 이하의 정수이다.
출력
세준이가 얻을 수 있는 최대 기쁨을 출력한다.