[BOJ/C++] 백준 28075 - 스파이

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

28074번: 모비스

총 N일동안 6가지 선택지 중 하나를 선택하며 얻을 수 있는 기여도의 가짓수를 출력하는 문제이다. 

브루트포스 알고리즘을 재귀함수를 이용하여 구현하였으며, 설계는 아래와 같다. 

1) 인수

• days : 현재 임무를 수행할 날짜
• sum : 현재까지 진척도를 모두 더한 기여도
• place : 이전 날에 임무를 수행한 장소

2) 종료 조건  : days 가 n일이 될 때, 즉 모든 날을 다 탐색한 경우 방법의 가짓수를 더하도록 하였다. 

3) 재귀 호출 

• 첫째 날은 이전 날에 임무를 수행하지 않았으므로, 모든 업무를 원래의 진척도로 수행한다. 
• 나머지 날은 이전 날에 같은 장소에서 업무를 수행하였다면 진척도를 절반으로, 다른 장소라면 원래 진척도대로 재귀호출하였다.

#include <iostream>
using namespace std; 

int info[2][3]; 
int n, m;
int ret = 0;

void solve(int days, int sum, int place) {
	if (days == n) {
		if (sum >= m) ret++; 
		return; 
	}
	if (days == 0) {
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 3; j++)
				solve(days + 1, sum + info[i][j], j); 
	}
	else {
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 3; j++)
				if (j == place)
					solve(days + 1, sum + info[i][j] / 2, j);
				else
					solve(days + 1, sum + info[i][j], j); 
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 3; j++)
			cin >> info[i][j]; 
	solve(0, 0, 0); 
	cout << ret << endl;
	return 0; 
}