코드업 3510번

이 글에서는 코드업 3510번 문제를 풀이해보도록 하겠습니다.

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

예산 관리

---

문제 설명

 

정보 선생님은 예산이 많은 부서에서 일하고 있다. 

학기말이 가까워지면서 부서의 예산을 가급적 모두 집행해야 될 상황이 되었다.

정보 선생님은 예산 범위를 넘지 않는 범위 내에서 다양한 활동을 하고 싶어한다.

지금 남은 예산(B)이 40이고(단위:만원), 예산을 사용할 수 있는 활동(N)이 6개가 있다.

6개의 활동에 각각 드는 비용은 7, 13, 17, 19, 29, 31이다.

여기서 40을 채울 수 있는 활동의 개수는 상관이 없다.

40을 넘지 않는 범위에서 활동 비용을 조합해보면, 

7 + 13 + 17 = 37

7 + 31 = 38

7 + 13 + 19 = 39

...

따라서 40을 초과하지 않으면서 예산을 최대로 사용할 수 있는 비용은 39이다.

정보 선생님을 도와 줄 수 있는 프로그램을 작성하시오.

---

입력

 

첫째 줄에 남은 예산(B)가 입력된다. (10 <= B <= 35,000)

둘째 줄에 예산을 사용할 수 있는 활동의 수(N)이 입력된다. (1 <= N <= 21)

셋째 줄에 공백을 기준으로 N개의 활동비가 양의 정수로 입력된다.

---

출력

 

남은 예산을 초과하지 않으면서 최대로 사용할 수 있는 비용액을 출력하시오.

문제를 해석해봅시다. 남은 예산 B와 N개의 활동, 각각의 활동비가 주어질 텐데 그 활동 중 몇 개만 선택해서 예산을 사용할 때 최대로 사용 가능한 예산은 얼마인지 묻고 있습니다. 활동을 고르는 모든 경우의 수별로 예산을 계산하여 최댓값을 찾는 방식으로 풀이하고자 하였습니다.

먼저 순서도를 그려보았습니다.

전체 순서도

핵심 함수 f의 순서도

이를 바탕으로 코드를 작성하면,

#include <stdio.h>

int b, n;
int a[30];
int max = -1;

void f(int tf, int sum, int m)
{
	if(m == n)
	{
		if(sum <= b)
		{
			max = max>sum?max:sum;
		}
		return;
	}
	else
	{
		sum = sum + tf*a[m];
		f(1, sum, m+1);
		f(0, sum, m+1);
	}
}

int main()
{
	scanf("%d %d", &b, &n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	
	f(1, 0, 0);
	f(0, 0, 0);
	
	printf("%d", max);
}

가능한 조합 중에서 최댓값을 찾을 때, 총합이 B보다 작아야 한다는 조건을 잊지 말아야 합니다. (저는 처음에 이를 잊고 코드를 짜다가 잘못 풀게 되었습니다.)

코드 설명은 아래와 같습니다.

예산과 활동 수 b와 n을 입력받고, 각 활동별 비용을 입력받아 배열 a에 저장합니다. 이제 함수 f를 실행해줍니다. f에는 tf, sum, m 3개의 인자가 전달되는데, m번째 활동을 할 것인지(tf==1) 안 할 것인지(tf==0), 그리고 현재까지 사용한 예산이 얼마인지(sum)을 의미합니다. 이렇게 가능한 활동 조합을 모두 탐색해보고, m==n이면, 즉 모든 활동에 대해 함수를 실행하고 그 중 b 이하인 최대의 sum값을 찾아 max에 저장하고, 이를 출력하면 문제를 해결됩니다.

---

이렇게 코드업 3510번 문제를 풀이해보았습니다.