[ boj : 20164 ] 홀수 홀릭 호석

www.acmicpc.net/problem/20164

20164번: 홀수 홀릭 호석

문제 : 규칙에 따라 나오는 수의 홀수의 개수를 세어주면 됩니다. 최소값과 최대값을 구해라

 

해설 : n이 최대 1e9-1 이므로 아무리 커봤자 9자리를 넘어가지 않습니다. 그래서 전 편하게 문자열을 사용했습니다.

1)0~i 까지

2)i~j 까지

3)j~끝 까지

 

이렇게 for문 3개를 돌려서 나누어주고 문자열의 길이가 2일때 1일때를 케이스로 또 나누어주면 됩니다.

문자열을 자르기 위해 substr 함수를 사용해 주었습니다.

매번 문자열->정수, 정수->문자열 이렇게 변환하는게 귀찮긴 한데 전 다른 방법은 복잡해서 구현에서 실수가 나올 것 같더라구요 ㅠ

 

#include<bits/stdc++.h>

using namespace std;

int Min=(int)1e9, Max=-1;

int get_odd(int x);
void solve(string s,int cnt);

int main()
{
	string s;
	cin >> s;

	solve(s,0);
	cout << Min << " " << Max;
	return 0;
}
void solve(string s,int cnt)
{
	int sum=0;
	if (s.length() == 1) {
		cnt += get_odd(stoi(s));
		Min = min(Min, cnt);
		Max = max(Max, cnt);
		return;
	}
	else if (s.length() == 2) {
		cnt += get_odd(stoi(s));
		int n = (s[0] - '0') + (s[1] - '0');		
		solve(to_string(n),cnt);
	}
	else if (s.length() >= 3) {
		cnt += get_odd(stoi(s));
		for(int i=1;i<s.length();i++)
			for (int j = i + 1; j < s.length(); j++) {
				string x = s.substr(0, i - 0);
				string y = s.substr(i, j - i);
				string z = s.substr(j, s.length() - j);
				int n = stoi(x) + stoi(y) + stoi(z);
				solve(to_string(n), cnt);
			}
				
	}
}
int get_odd(int x)
{
	int ret=0;
	while (x > 0)
	{
		if ((x%10) % 2 == 1)
			ret++;
		x /= 10;
	}
	return ret;
}