알고리즘 스터디

Google Kickstart 2020 Round A

Allocation

N개의 집이 있고, i번째 집의 가격은 Ai 달러이다. 총 재산은 B달러만큼 가지고 있다.

살수있는 집의 최대 갯수를 구하는 문제이다.

 

Limits

Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ B ≤ 10^5.
1 ≤ Ai ≤ 1000, for all i.

 

Test set 1

1 ≤ N ≤ 100.

Test set 2

1 ≤ N ≤ 10^5.

 

C++를 사용한 제 풀이입니다.

#include <iostream>
#include <algorithm>

using namespace std;

int n, b, a[100000];

void solve() {
	cin >> n >> b;

	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	sort(a, a + n);

	int ans = 0;

	for (int j = 0; j < n; ++j) {
		if (b >= a[j]) {
			b -= a[j];
			++ans;
		}
	}

	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	for (int i = 1; i <= t; ++i) {
		cout << "Case #" << i << ": ";
		solve();
	}
}

프로그래머스랑 조금 다르게 cin부터 해야돼서 입력받는 부분은 다른 사람이 했던 걸 조금 참조하긴 했어요..

이번 것도 배열을 이용해서 풀었는데 집 가격을 우선 오름차순으로 정리해 싼 집부터 구매했어요

구매할때마다 ans를 1씩 증가시켜줬고 case별로 출력했네요.

프로그래머스 난이도로 생각해보면 1레벨 정도가 아닐까 생각해요