[백준 28075] 스파이 (C++)

문제

---

스파이 민겸이는 이웃 나라와의 평화를 위해 N일간 임무를 수행한다.

민겸이는 정보 수집과 감시 2가지 임무를 수행한다. 각 임무는 수족관, 시청, 학교에서 수행할 수 있다. 두 임무는 성격이 크게 다르기 때문에 하루에 한 가지 임무만 수행할 수 있으며, 수족관, 시청, 학교는 멀리 떨어져 있기 때문에 하루에 한 가지 장소에서만 임무를 수행할 수 있다. 또한, 민겸이는 반드시 하루에 최소 하나의 임무를 수행해야 한다.

 

다시 말해, 민겸이는 하루에 위 표의 6가지 행동 중 하나를 선택하여 할 수 있다.

민겸이는 각 장소에서 각 임무를 수행할 때, 임무 완수를 위한 진척도를 얻을 수 있다. 그러나 민겸이는 스파이이기 때문에, 같은 장소에서 오래 근무하면 사람들의 눈에 띄어 얻을 수 있는 진척도가 낮아진다. 민겸이가 전날에 임무를 수행한 곳과 같은 장소를 선택하면 그 날은 원래의 절반에 해당하는 진척도만 얻을 수 있다. 이때, 장소가 같다면 임무가 달라도 얻는 진척도는 원래의 절반이 됨에 유의하자.

민겸이의 기여도는 얻은 진척도의 합이다. 각 장소에서 각 임무를 수행했을 때 얻을 수 있는 진척도가 주어질 때 민겸이가 M 이상의 기여도를 얻을 수 있는 임무 수행 방법이 몇 가지인지 구하라.

입력

---

첫째 줄에는 민겸이가 임무를 수행하는 총 일수 N$N$과 민겸이가 얻고 싶은 최소 기여도 M$M$이 공백으로 구분되어 주어진다.

둘째 줄에 민겸이가 정보 수집 임무를 수족관, 시청, 학교에서 수행했을 때 얻을 수 있는 진척도가 순서대로 공백으로 구분되어 주어진다.

셋째 줄에 민겸이가 감시 임무를 수족관, 시청, 학교에서 수행했을 때 얻을 수 있는 진척도가 순서대로 공백으로 구분되어 주어진다.

출력

---

민겸이가 기여도를 M 이상 얻을 수 있는 임무 수행 방법이 몇 가지인지 출력한다.

 

제한

---

•  1 ≤ N ≤ 8
•  1 ≤ M ≤ 25
• 주어지는 모든 진척도는 0 이상 10 이하의 짝수이다.
• 주어지는 모든 수는 정수이다.

문제 풀이

---

브루트포스 문제.

 

모든 가능한 수를 구한 후, 해당 경우에서 얻을 수 있는 기여도가 M 이상인 경우를 세어주면 된다.

첫째 날일 때에는 아무 일이나 해도 상관 없지만, 둘째날부터는 이전에 한 장소라면 기여도가 1/2이 된다. 따라서 함수의 매개변수에 이전 장소를 저장하는 변수와, 현재까지의 기여도를 저장하는 변수를 넣어준 후, 날짜가 진행될 수록 해당 장소와 수행한 임무에 따라 현재까지의 기여도를 변경시킨다. N번째 날일 때에는 기여도가 M이상인지 확인해주면 된다.

 

아래는 코드.

#include <iostream>
#include <cmath>
using namespace std;
int N, M;
int* arr;
int answer;

void find(int day, int prevDayIndex, int sum)
{
	if (day == N)
	{
		for (int i = 0; i < 6; i++)
		{
			if (abs(i - prevDayIndex) == 3 || i == prevDayIndex)
			{
				if (sum + arr[i] / 2 >= M)
				{
					answer++;
				}
			}
			else
			{
				if (sum + arr[i] >= M)
				{
					answer++;
				}
			}
		}
		return;
	}
	else if (day == 1)
	{
		for (int i = 0; i < 6; i++)
		{
			find(day + 1, i, arr[i]);
		}
	}
	else
	{
		for (int i = 0; i < 6; i++)
		{
			if (abs(i - prevDayIndex) == 3 || i == prevDayIndex)
			{
				find(day + 1, i, sum + arr[i] / 2);
			}
			else
			{
				find(day + 1, i, sum + arr[i]);
			}
		}
	}
}

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

	arr = new int[6];
	cin >> N >> M;
	for (int i = 0; i < 6; i++)
	{
		cin >> arr[i];
	}
	find(1, -999, 0);
	cout << answer << "\n";
	return 0;
}