(2022.06.24) 어떤 알고리즘을 사용해야 할까?

[BurningFalls]

문제

활을 쏴서 과녁에 맞춰 점수를 얻는다.

총 N 종류의 활이 각각 하나씩 준비되어 있고, 각 화살은 특정 무게 W와 각 화살을 쐈을 때 맞추는 점수 S를 갖고 있다.

N 종류의 화살 중 몇 개를 골라 점수를 최대한 많이 얻고자 한다.

그런데, 근손실로 인해 총 K 무게만큼의 화살밖에 쏘지 못한다.

얻을 수 있는 최대 점수를 구해보자.

입력

첫째 줄에 화살의 개수 N과 가능한 총 무게 K가 주어진다.

둘째 줄에 N개의 각 화살 무게 W가 주어진다.

셋째 줄에 N개의 각 화살을 쐈을 때 얻는 점수 S가 주어진다.

출력

총합 무게 W를 넘지 않으면서 얻을 수 있는 최대 점수를 출력한다.

제한

• 시간 제한: 2초
• 메모리 제한: 512MB
• 1 ≤ N ≤ 100
• 1 ≤ K ≤ 100,000
• 1 ≤ W ≤ 100,000
• 0 ≤ S ≤ 1,000

예제 입력

4 7

6 4 3 5

13 8 6 12

예제 출력

14

---

직접 코딩할 필요 없이 다음 질문들에 대해서 한번 생각해보자.

Q1. 다음 문제를 최대한 효율적으로 풀려면, 어떤 알고리즘을 사용해야 할까?

Q2. 해당 알고리즘을 구현해서 위 문제를 해결할 수 있는가?

Q3. 문제의 제한 조건이 어떻게 달라지면, 기존의 Q1 방식으로 문제를 해결할 수 없게 되는가?

Q4. 만약 화살이 종류별로 하나씩 있는 것이 아니라 종류별로 여러 개(무한 개) 존재한다면, 구현이 어떻게 달라져야 할까?

Q5. 위의 Q4 문제를 구현해서 해결할 수 있는가?

(직접 만든 거라 문제에 오류가 있거나 설명이 불충분할 수도 있음)