SWEA1265.달란트2
#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;이런식으로 중복탐색 안하려고 조건 거는데,
이런문제에서는 조건을걸면 안됨.
- DFS처음 스타트를 나는 0으로하자. 그래야 마지막 depth에서 처리하기 편하다.
이 문제는 그냥 수학 문제여서 DFS로 풀면 시간초과나온다.
중간값정해서 나머지만큼+하면되는문제.
Author And Source
이 문제에 관하여(SWEA1265.달란트2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@imalive77/SWEA1265.달란트2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)