SWEA1265.달란트2

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=5&contestProbId=AV18R8FKIvoCFAZN&categoryId=AV18R8FKIvoCFAZN&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=5&pageSize=10&pageIndex=1

#include <string>
#include <algorithm>
#include <vector>
#include <deque>
#include <iostream>

using namespace std;
bool chk[101] = { false, };
int target(0);
int answer(0);
deque<int> dTemp;
void dfs(int coin, int depth)
{
	if (depth == target)
	{
	
		int iTemp(1);
		for (int i = 0; i < dTemp.size(); i++)
		{
			iTemp *= dTemp[i];
		}
		if (iTemp > answer)		answer = iTemp;
		dTemp.pop_back();
		return;
	}

	for (int i = 1; i < coin; i++)
	{
		if (coin - i < 1)	return;
		if ((coin-i>=1))
		{
			
			//chk[i] = true;
			if(depth + 1 == target)		dTemp.emplace_back(coin);//나머지루틴 다넣는다
			else						dTemp.emplace_back(i);

			dfs(coin - i, depth + 1);
			dTemp.pop_back();
			//chk[i] = false;
		}
	}
}
int main() {
	
	int T;	cin >> T;
	for (int b = 1; b < T; b++)
	{
		target = 0;			answer = 0;		dTemp.clear();
		for (int i = 0; i < 101; i++)
		{
			chk[i] = false;
		}
		int coin;	cin >> coin;
		int division; cin >> division;
		target = division;

		dfs(coin , 0);
		//for (int i = 1; i < coin; i++)
		//{
		//	chk[i] = true;
		//	vTemp.emplace_back(i);

		//	dfs(coin-i, 1);
		//	chk[i] = false;
		//	vTemp.clear();
		//}
	

		cout << "#" << b << " " << answer << "\n";
	}
	return 0;
}

1.이문제 풀다가 보통 chk[i] = true;이런식으로 중복탐색 안하려고 조건 거는데,
이런문제에서는 조건을걸면 안됨.

2. DFS처음 스타트를 나는 0으로하자. 그래야 마지막 depth에서 처리하기 편하다.

이 문제는 그냥 수학 문제여서 DFS로 풀면 시간초과나온다.
중간값정해서 나머지만큼+하면되는문제.