[백준 20164] 홀수 홀릭 호석

문제

www.acmicpc.net/problem/20164

20164번: 홀수 홀릭 호석

 

풀이

 

문제의 연산을 살펴보면 숫자를 세 개의 숫자로 분할하거나, 숫자의 자릿수들을 검사하므로 편의를 위해 다루는 숫자들을 문자열로 처리하기로 하며, 이 문제의 시작이자 끝인 분할하는 함수를 생각해봅시다.

 

1. 숫자를 분할하고 새로운 숫자를 만들어내는 연산을 한 후, 새로운 숫자도 연산을 거쳐야 하므로 분할하는 과정은 재귀를 사용해 해결해야 함을 알 수 있습니다.

 

2. 아래의 그림과 같이 길이가 k$(k>= 3)$인 숫자를 분할한다고 했을 때, 2개의 인덱스$(1 <=(i, j)< k)$를 뽑아 칸막이를 세운다고 생각하면 세 개의 수를 만들 수 있고( num1 : [0, i) , num2 : [i, j) , num3 : [j, k) ), 어떻게 나누는지에 따라서 여러 가지 숫자로 바뀌기에 최종 연산의 최대 값과 최소 값이 다르게 됩니다. 

3. 길이가 2인 숫자는 각 자릿수를 더한 수로 새로운 수를 만드므로 각 문자의 자릿수를 더한 후, 다시 재귀로 넘겨줍니다.

 

4. 종료조건인 길이가 1인 숫자는 현재까지 연산 결과의 홀수 개수와 처음 주어진 n의 홀수 개수를 더해서 최대 값과 최소 값을 갱신하면 됩니다.

 

5. 4번을 제외한 위의 과정을 진행하며 새로운 수를 만들 때마다, 그 수의 자릿수들 중 홀 수 개수를 구해(cal) 현재까지의 홀수 개수를 담는 sum에 더해주며 재귀로 넘겨줍니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()

string n, nx;
int a, b, c, miv, mav, ret;

int cal(string x) {
	ret = 0;
	for (int i = 0; i < sz(x); i++)
		ret += (x[i] - '0') % 2;
	return ret;
}

void divide(string x, int sum) {
	if (sz(x) >= 3) {
		for (int i = 1; i < sz(x); i++) {
			for (int j = i + 1; j < sz(x); j++) {
				a = stoi(x.substr(0, i));
				b = stoi(x.substr(i, j - i));
				c = stoi(x.substr(j));
				nx = to_string(a + b + c);
				divide(nx, sum + cal(nx));
			}
		}	
	}
	else if (sz(x) == 2) {
		nx = to_string(x[0] + x[1] - '0' * 2);
		divide(nx, sum + cal(nx));
	}
	else if (sz(x) == 1) {
		miv = min(miv, sum + cal(n));
		mav = max(mav, sum + cal(n));
	}
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	miv = INT_MAX, mav = INT_MIN;
	divide(n, 0);
	cout << miv << " " << mav;
}