<백준> 18429

근손실

문제
웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다.
다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 수 있다. 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가하게 된다. 이 때 몇몇 운동 키트들의 중량 증가량이 같을 수 있으나, 서로 다른 운동 키트로 간주한다. 각각의 운동 키트는 N일 동안 한 번씩만 사용할 수 있다.
대학원생은 운동 기간동안 항상 중량이 500 이상으로 유지가 되도록 N일간의 운동 플랜을 세우고자 한다. 1일차부터 N일차까지의 모든 기간동안, 어떤 시점에서라도 중량이 500보다 작아지지 않도록 해야 한다.
예를 들어 N=3, K=4일 때, 각 운동 키트의 중량 증가량이 다음과 같다고 가정하자.

입력
첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 8, 1 ≤ K ≤ 50) 둘째 줄에 각 운동 키트의 중량 증가량 A가 공백을 기준으로 구분되어 주어진다. (1 ≤ A ≤ 50)

출력
N일 동안 N개의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력한다.

모든 순서를 고려해야 하므로 백트래킹으로 모든 경우의 수를 탐색한다.
각 날마다 중량 증가량 v[i]를 더하고, 하루마다 감소하는 값 k를 빼며 누적값을 갱신한다.
이 과정에서 누적값(total)이 500 미만이 되면 더 이상 진행할 수 없으므로 가지치기하고,
끝까지 500 이상을 유지한 경우만 카운트한다.
따라서 total + v[i] - k를 매번 계산하며 다음 상태로 넘기는 것이 핵심이다

int n, k;
int result;
vector<int> v;

bool visited[8];

void DFS(int cnt, int total)
{
	if (total < 500)
		return;
	if (cnt == v.size())
	{
		result++;
		return;
	}

	for (int i = 0; i < v.size(); i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			DFS(cnt + 1, total + v[i] - k);
			visited[i] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}

	DFS(0, 500);

	cout << result;
}