[SWEA 7206] 숫자 게임 (C++)

문제 링크: https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWlGyBQqaEgDFASG

SW Expert Academy

1. 주의할 점

- Check[idx] 배열을 만들어서 값을 기록해놓는다(idx의 경우 최대 몇 번의 Turn이 가능한지)

 

2. 구현

- 초기에 Check[] 배열을 전부 -1로 초기화하고 한 자리 숫자는 0으로 초기화 한다

- DFS(Sum,Tot,Ss,V)를 통해 해당 Ss를 몇 부분으로 쪼갤 수 있는지 벡터 V에 담는다

- Sum==Tot인 경우, V의 Size가 1일때는 return(1 덩이이므로)  Cal(Ss,V) 함수를 실행하여 Check[Stoi(ss)]를 최대로 초기화해준다

- Cal(Ss,V) 함수는 V에 담긴 부분으로 Ss를 나누고, 각 원소들을 곱한 값을 Tmp에 저장하고 Check[Tmp]가 -1이 아니라면 Check[Tmp]를 반환하고 -1인 경우, DFS(0,Tmp의 문자열 크기, Tmp의 문자열, Vv)를 수행한다. 새로운 Vv 벡터를 만들어서 기존 V 벡터와 겹치지 않도록 한다

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int result;
int check[100000];
int cal(string s, vector<int> v);

void dfs(int sum, int tot, string ss, vector<int> v) {
	if (sum == tot) {
		if (v.size() == 1) return;
		check[stoi(ss)] = max(check[stoi(ss)], cal(ss, v));
		return;
	}
	for (int i = 1; i <= tot - sum; i++) {
		v.push_back(i);
		dfs(sum + i, tot, ss, v);
		v.pop_back();
	}
}

int cal(string s, vector<int> v) {
	int tmp = 1, cnt = 0;
	for (int i = 0; i < v.size(); i++) {
		int len = v[i];
		string ss = s.substr(cnt, len);
		int val = stoi(ss);
		tmp *= val;
		cnt += len;
	}
	if (check[tmp] == -1) {
		string st = to_string(tmp);
		vector<int> vv;
		dfs(0, st.size(), st, vv);
	}
	return check[tmp] + 1;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test;
	cin >> test;
	for (int i = 0; i < 100000; i++)
		check[i] = -1;
	for (int i = 0; i < 10; i++)
		check[i] = 0;
	for (int t = 1; t <= test; t++) {
		result = 0;
		string str;
		cin >> str;
		vector<int> v;
		dfs(0, str.size(), str, v);
		cout << "#" << t << " " << check[stoi(str)] << '\n';
	}
	system("pause");
	return 0;
}