[Codeup] 3510. 예산 관리

1. 문제 링크

https://codeup.kr/problem.php?id=3510

코드업

 

2. 문제 풀이

N이 작기 때문에, 완전 탐색 형태로 풀어도 된다.

예산이 넘지 않는 선에서 후보를 포함, 제외 시켜가면서 최대값을 갱신하면 도니다.

 

3. 아이디어

1. 재귀 기반 완전 탐색 형태로 탐색을 진행한다.
2. depth 형태로 0번째 값부터 탐색해서, n-1에 도달하면 탐색을 끝낸다.
    2-1. 이때 예산을 넘지 않는다면 해당 depth의 활동을 진행하는 케이스로 탐색을 한다.
    2-2. 해당 depth에서 진행하지 않는 케이스에 대한 탐색을 진행한다.
3. 매 탐색 마다 가장 크게 사용된 예산 값을 갱신하면 최대값이 나온다.

 

3. 아이디어 ( Case B )

- 큰 차이는 없지만, 정렬를 이용한 방법을 생각했다.
- n이 작기 때문에 정렬하는데 큰 부담이 없다.
- 정렬을 해두면, 예산을 넘는 뒤쪽 후보를 한 번에 잘라낼 수 있다.

 

4. 구현

※ C++ Source Code

#include <iostream>
using namespace std;
int budget;
int ans = 0;
int n;
int money[25];

void back(int value, int depth)
{
	if (value <= budget) // 예산 선에서 가장 큰 값 갱신
	{
		if (ans < value) ans = value;
	}

	if (depth == n - 1) return;

	if (value + money[depth + 1] <= budget) // 예산 넘지 않으면 활동 진행
	{
		back(value + money[depth + 1], depth + 1);
	}
	back(value, depth + 1); // 활동 안함
}

int main(void)
{
	cin >> budget;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> money[i];
	}
	
	back(0, -1);
	cout << ans;
}

 

4. 구현 (Case B)

※ C++ Source Code

#include <iostream>
#include <algorithm>
using namespace std;
int budget;
int money[25];
int n;
int ans = 0;

void dfs(int depth, int sum) 
{
	ans = max(ans, sum);

	for (int i = depth; i < n; i++) {
		if (sum + money[i] > budget) break; // 정렬했으므로 뒤도 전부 불가능

		dfs(i + 1, sum + money[i]);
	}
}

int main(void)
{
	cin >> budget;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> money[i];
	}

	sort(money, money + n);

	dfs(0, 0);
	cout << ans;
}