장난감 가격들이 배열 형태로 주어져 있고, 손에 들고 있는 금액 K가 있습니다. 목표는 이 금액으로 구매할 수 있는 장난감의 최대 개수를 구하는 것입니다. 배열의 각 요소는 장난감 하나의 가격을 의미하므로, 배열의 크기가 곧 전체 장난감의 수가 됩니다.
핵심 아이디어
가장 효율적인 방법은 가격 배열을 오름차순으로 정렬하는 것입니다. 저렴한 장난감부터 우선적으로 구매해야, 한정된 예산으로 최대한 많은 장난감을 살 수 있기 때문입니다. 이는 대표적인 그리디(Greedy) 알고리즘 문제입니다.
입출력 예시 1
toyprices[] = { 10, 20, 12, 15, 50, 30 }, K = 50출력
구매할 수 있는 장난감의 최대 개수 : 3
설명 — 가격을 오름차순으로 정렬하면 { 10, 12, 15, 20, 30, 50 }이 됩니다.
첫 번째 장난감 구매: K=50, 개수=1, 남은 금액 = 40 (50-10) 두 번째 장난감 구매: K=40, 개수=2, 남은 금액 = 28 (40-12) 세 번째 장난감 구매: K=28, 개수=3, 남은 금액 = 13 (28-15) 다음 장난감 가격은 20인데 남은 금액이 13이므로 더 이상 구매 불가 → 정답은 3
입출력 예시 2
toyprices[] = { 50, 40, 30, 20, 10 }, K = 25출력
구매할 수 있는 장난감의 최대 개수 : 1
설명 — 25는 10과 20보다 크지만, 두 개를 동시에 살 수는 없습니다(10+20=30 > 25). 따라서 최대 구매 개수는 1입니다.
알고리즘 접근 방법
정수 배열
price[]에 장난감 가격들을 저장합니다.함수
maxToys(int price[], int N, int K)는 가격 배열, 배열의 길이 N, 보유 금액 K를 매개변수로 받습니다.구매 가능한 장난감 수를 저장할 변수
toycount를 선언하고 0으로 초기화합니다.현재까지 지출한 금액을 추적하는 변수
spent를 사용합니다.sort(price, price + N);을 사용해 가격 배열을 오름차순으로 정렬합니다.가장 저렴한
price[0]부터 비싼 가격 순서대로 배열을 순회합니다.각 장난감 가격을
spent에 더했을 때 K 이하라면 구매 가능하므로toycount를 1 증가시키고,spent를 갱신합니다.배열이 정렬되어 있으므로, 예산을 초과하는 순간 반복문을 종료하면 됩니다.
최종적으로
toycount가 구매 가능한 장난감의 최대 개수입니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int maxToys(int price[], int N, int K){
int toycount = 0;
int spent = 0; // 지출한 금액은 항상 K 이하로 유지
// 저렴한 가격이 앞에 오도록 정렬
sort(price, price + N);
for (int i = 0; i < N; i++) {
if (spent + price[i] <= K){
spent = spent + price[i];
toycount++;
} else
break; // 이미 정렬된 배열이므로 즉시 종료
}
return toycount;
}
int main(){
int budget = 100;
int toyprice[] = { 10, 120, 50, 11, 20, 100, 10, 90, 12, 15 };
int N = 10;
cout << "구매할 수 있는 장난감의 최대 개수 : " << maxToys(toyprice, N, budget);
return 0;
}출력 결과
구매할 수 있는 장난감의 최대 개수 : 6
설명 — 정렬 후 가격은 { 10, 10, 11, 12, 15, 20, 50, 90, 100, 120 }이 되며, 앞에서 여섯 개를 구매하면 총 78원으로 예산 100원 이내입니다. 일곱 번째 장난감(50원)을 추가하면 128원이 되어 예산을 초과하므로 정답은 6입니다.
시간 복잡도
정렬에 O(N log N), 배열 순회에 O(N)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다. 공간 복잡도는 추가 배열 없이 제자리 정렬을 사용하므로 O(1)입니다.