백준 - 18429 근손실 (C++)

Pixabay로부터 입수된 Steve Buissinne님의 이미지 입니다.

 

---

 

https://www.acmicpc.net/problem/18429

18429번: 근손실

 

 이번 문제는 운동 일수 N, 운동 키트 개수 K, 그리고 K개의 (운동 키드 별) 중량 증가량이 주어졌을 때, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 구하는 문제이다. 이 문제의 알고리즘 분류에서도 확인할 수 있듯, 모든 경우를 검사해야 하는 문제이다. 그리고 예제의 그림(표)에서도 확인할 수 있듯, 만약 운동 키트가 3개라면 1번-2번-3번, 1번-3번-2번 등의 모든 경우를 확인해야 한다.

 

예제

 

 위의 예제를 통해 문제의 흐름을 파악해보자. 이미지에는 안나와있지만 K는 4이다. 만약 위와 같이 주어질 경우, 아래처럼 운동을 할 수 있다.

 

예제의 순서

 

만약 운동을 1번-2번-3번 순으로 한다고 하자. 처음에는 중량이 500이다. 그리고 하루가 지나면 N만큼 줄어들기 때문에 중량은 500 - 4 = 496이 된다. 그리고 1번 운동 키트의 중량 증가량만큼 중량이 증가하므로 496 + 3 = 499이다. 500 미만이 되었기에 1번-2번-3번 순서는 실패이다. 이런 식으로 운동 순서들을 미리 정한 후, 매 운동마다 중량이 500 미만이 되는지를 검사하면 된다.

 

 가능한 모든 운동의 순서를 구하기 위해서는 순열을 구하는 방식을 응용할 수 있다. 왜냐하면 1번-2번-3번과 1번-3번-2번은 다른 경우이기 때문이다. 

 

int answer = 0;

void Check(int cnt)
{
	if (cnt >= N)
	{
		bool success = Exercise();

		if (success)
			++answer;

		return;
	}

	for (int idx = 0; idx < N; ++idx)
	{
		if (used[idx] == false)
		{
			used[idx] = true;
			exerciseOrder.push_back(idx);

			Check(cnt + 1);

			exerciseOrder.pop_back();
			used[idx] = false;
		}
	}
}

 

위의 코드는 운동의 순서를 구하는 함수이다. 인자의 cnt는 현재 선택된 운동 키트의 개수이다. 모든 운동 키트를 처음부터 검사한다. 만약 현재 idx번 운동 키트가 선택되지 않았다면 이를 선택한 후 재귀를 통해 탐색을 진행한다. 만약 cnt가 모든 운동 키트 개수와 같다면, 매 중량이 500 미만이 되는지 아닌지를 검사한다. 만약 500미만이 되지 않는다면, answer를 1 증가시킨다.

 

#define MIN_WEIGHT_THRESHOLD 500

bool Exercise()
{
	int val = MIN_WEIGHT_THRESHOLD;

	for (int i = 0; i < exerciseOrder.size(); ++i)
	{
		int currentExercise = exerciseOrder[i];

		val = val + exercise[currentExercise] - K;

		if (val < MIN_WEIGHT_THRESHOLD)
			return false;
	}

	return true;
}

 

이 함수는 매 중량이 500 미만이 되는지를 검사하는 함수이다. 매 중량은 현재 중량 + 중량 증가량 - K이기에, 이 값이 500 미만이 되면 바로 false를 반환하고 그렇지 않다면 반복문을 마친 후 true를 반환한다.

 

#include <iostream>
#include <vector>
#define MAX 51
#define MIN_WEIGHT_THRESHOLD 500
using namespace std;

int answer = 0;
int N, K;
int exercise[MAX];
bool used[MAX];
vector<int> exerciseOrder;

bool Exercise()
{
	int val = MIN_WEIGHT_THRESHOLD;

	for (int i = 0; i < exerciseOrder.size(); ++i)
	{
		int currentExercise = exerciseOrder[i];

		val = val + exercise[currentExercise] - K;

		if (val < MIN_WEIGHT_THRESHOLD)
			return false;
	}

	return true;
}

void Check(int cnt)
{
	if (cnt >= N)
	{
		bool success = Exercise();

		if (success)
			++answer;

		return;
	}

	for (int idx = 0; idx < N; ++idx)
	{
		if (used[idx] == false)
		{
			used[idx] = true;
			exerciseOrder.push_back(idx);

			Check(cnt + 1);

			exerciseOrder.pop_back();
			used[idx] = false;
		}
	}
}

int main()
{
 	ios_base::sync_with_stdio(0);
	std::cout.tie(0);
	std::cin.tie(0);

	cin >> N >> K;

	for (int n = 0; n < N; ++n)
		cin >> exercise[n];

	Check(0);

	cout << answer << endl;
	
	return 0;
}