문제

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

풀이

조합, 백트래킹 (오답)

혼자 고민해서 2시간 반 가량을 풀었는데,, 계속 오답이 나왔다,, 🥲

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N;
int minCnt = 1e9, maxCnt = -1;

bool isOdd(int x){
	return x % 2 != 0;
}

int calcOddNum(int x){
	int cnt = 0;
	while(x / 10 > 0){
		if(isOdd(x % 10)) cnt++;
		x /= 10;
	}
	if(isOdd(x)) cnt++;
	return cnt; 
}

int calcDigit(int x) {
	int digit = 1;
	while(x / 10 > 0){
		digit++;
		x /= 10;
	}
	return digit;
}

void dfs(int now, int digit, int cnt){
	if(digit == 1){
		if(isOdd(now)) cnt++;

		// 홀수의 최소, 최대 개수 갱신 
		maxCnt = max(maxCnt, cnt);
		minCnt = min(minCnt, cnt);
		
		return;
	}

	if(digit == 2){
		int sum = (now % 10) + (now / 10);
		int newDigit = calcDigit(sum);
		int newOddCnt = calcOddNum(sum);
		dfs(sum, newDigit, cnt + newOddCnt);
	}else{
		// 자리수: k, 3개로 분할: k-1_C_2 (3 <= k <= 9)
		// k-1개 중에 2개 선택
		vector<bool> check(digit - 1, 1);
		check[0] = check[1] = 0;
		
		do{
			vector<int> split;
			for(int i = 0; i < check.size(); i++){
				if(check[i]) split.push_back(i);
			}

			// 1_2v3_4v5
			// 12 34 5
			string str = to_string(now);
			string s1 = str.substr(0, split[0] + 1);
			string s2 = str.substr(split[0] + 1, split[1] - split[0]);
			string s3 = str.substr(split[1] + 1);
			
			int sum = stoi(s1) + stoi(s2) + stoi(s3);
			int newDigit = calcDigit(sum);
			int newOddCnt = calcOddNum(sum);
			dfs(sum, newDigit, cnt + newOddCnt);
		}while(next_permutation(check.begin(), check.end()));
	}
}

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

	cin >> N;
	
	int digit = calcDigit(N);
	int oddCnt = calcOddNum(N);
	if(digit == 1){
		cout << oddCnt << " " << oddCnt << endl;
		return 0;
	}
	
	dfs(N, digit, oddCnt);
	cout << minCnt << " " << maxCnt;

	return 0;
}

조합 대신 이중 반복문 사용

결국 다른 사람들의 풀이를 참고했는데, 숫자의 자릿수를 직접 계산하지 않고 문자열의 길이로 구하는 게 더 쉽다. (시간도 더 적게 걸린다.)

그리고 next_permutation을 사용한 풀이는 계속 오답이 나와서 이중 반복문으로 바꿔서 풀었더니 정답이 나왔다,, 숫자의 최대 자리수가 9자리여서 이중 반복문으로 풀어도 시간초과가 발생하지 않는다.

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N;
int minCnt = 1e9, maxCnt = -1;

bool isOdd(int x){
	return x % 2 == 1;
}

int calcOddNum(string s){
	int cnt = 0; 
	for(int i = 0; i < s.size(); i++){
		if(isOdd(s[i] - '0')) cnt++;
	}
	return cnt++;
}

void dfs(string now, int cnt){
	int digit = now.size();
	
	if(digit == 1){
		cnt += calcOddNum(now);

		// 홀수의 최소, 최대 개수 갱신 
		maxCnt = max(maxCnt, cnt);
		minCnt = min(minCnt, cnt);
		
		return;
	}

	if(digit == 2){
		cnt += calcOddNum(now);
		int sum = (now[0] - '0') + (now[1] - '0');
		dfs(to_string(sum), cnt);
	}else{
		cnt += calcOddNum(now);
		
		for(int i = 1; i < digit - 1; i++){ // 최대 9자리 
			string s1, s2, s3;
			for(int j = i + 1; j < digit; j++){
				s1 = now.substr(0, i);
				s2 = now.substr(i, j - i);
				s3 = now.substr(j);
				int sum = stoi(s1) + stoi(s2) + stoi(s3);
				dfs(to_string(sum), cnt);
			}
		}
	}
}

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

	string N; 
	cin >> N;
	
	dfs(N, 0);
	cout << minCnt << " " << maxCnt;

	return 0;
}