5406 : C07 - 알고 마켓 (ALGO-MARKET)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
ALGO-MARKET에는 $N$ 개의 상품이 판매되고 있습니다. $i$ 번째 상품의 가격은 $C_i$ 원입니다.
다음 $Q$ 개의 질문에 각각 답하는 프로그램을 작성하십시오.
• 질문: $X_j$ 원 이하의 예산으로 최대 몇 개의 상품을 구매할 수 있는가?
[제약 조건]
• $1 \le N, Q \le 100{,}000$
• $1 \le C_i \le 10^9$
• $0 \le X_j \le 10^{14}$
• 입력되는 모든 값은 정수입니다.
다음 $Q$ 개의 질문에 각각 답하는 프로그램을 작성하십시오.
• 질문: $X_j$ 원 이하의 예산으로 최대 몇 개의 상품을 구매할 수 있는가?
[제약 조건]
• $1 \le N, Q \le 100{,}000$
• $1 \le C_i \le 10^9$
• $0 \le X_j \le 10^{14}$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 정수 $N$ 이 주어집니다.
둘째 줄에 $C_1, C_2, \dots, C_N$ 이 공백으로 구분되어 주어집니다.
셋째 줄에 질문의 개수 $Q$ 가 주어집니다.
넷째 줄부터 $Q$ 개의 줄에 걸쳐 각 질문의 예산 $X_j$ 가 한 줄에 하나씩 주어집니다.
둘째 줄에 $C_1, C_2, \dots, C_N$ 이 공백으로 구분되어 주어집니다.
셋째 줄에 질문의 개수 $Q$ 가 주어집니다.
넷째 줄부터 $Q$ 개의 줄에 걸쳐 각 질문의 예산 $X_j$ 가 한 줄에 하나씩 주어집니다.
출력 설명
각 질문에 대해 구매 가능한 최대 상품 개수를 한 줄에 하나씩 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
300 100 400 100 500
3
500
250
40
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
2
0도움
가격이 저렴한 상품부터 우선적으로 구매하는 그리디(Greedy) 방식을 적용합니다.
상품 가격을 오름차순 정렬하면 $100, 100, 300, 400, 500$ 원입니다.
• $X_1 = 500$ 원: $100 + 100 + 300 = 500$ 원으로 최대 $3$ 개 구매 가능
• $X_2 = 250$ 원: $100 + 100 = 200$ 원으로 최대 $2$ 개 구매 가능
• $X_3 = 40$ 원: 어떤 상품도 구매할 수 없으므로 $0$ 개
상품 가격을 오름차순 정렬하면 $100, 100, 300, 400, 500$ 원입니다.
• $X_1 = 500$ 원: $100 + 100 + 300 = 500$ 원으로 최대 $3$ 개 구매 가능
• $X_2 = 250$ 원: $100 + 100 = 200$ 원으로 최대 $2$ 개 구매 가능
• $X_3 = 40$ 원: 어떤 상품도 구매할 수 없으므로 $0$ 개