[백준 C++] 20164 홀수 홀릭 호석

문제

호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 홀수 홀릭에 빠진 호석이는 가지고 있는 수 N을 일련의 연산을 거치면서, 등장하는 숫자들에서 홀수를 최대한 많이 많이 보고 싶다.

하나의 수가 주어졌을 때 호석이는 한 번의 연산에서 다음과 같은 순서를 거친다.

수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.
수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다.
수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.
수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각한다.
호석이는 연산이 종료된 순간에 종이에 적힌 수들을 모두 더한다. 그렇게 최종적으로 얻은 수를 최종값이라고 하자. 예를 들어, 시작하는 수가 82019 라고 하자. 그럼 아래와 같이 나누게 되면 5개의 홀수를 볼 수 있기 때문에, 최종값이 5가 된다.

시작할 때 호석이가 가진 수를 N 이라고 했을 때, 만들 수 있는 최종값 중 최솟값과 최댓값을 구해주자.

입력

첫번째 줄에 호석이가 처음 시작할 때 가지고 있는 수 N 이 주어진다.

출력

첫 번째 줄에 호석이가 만들 수 있는 최종값 중에서 최솟값과 최댓값을 순서대로 공백으로 구분하여 출력한다.

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

풀이

재귀적 구조

• 무조건 종료조건은 하나의 코드블럭에서 처리한다.
• 값 연산하는 과정이 있고, 복잡하다면 최대한 전역변수에서 값연산하도록.
  예로들면, 어떤 vector의 주소를 받아와서 그 vector에 저장하는등.

이 두가지를 명심하고 코드를 짜면 어렵지 않게 풀 수 있다.

수를 가위로 쪼개다보면 언제는가는 1자리 가될것이고,
그럼이때 문제의 조건에의해 종료하도록 코드를 짜야한다.

수와 문자열을 왓다갓다 연산해야하므로, 필요에따라 해당 변환과정을 함수로 만들어도 좋을것 같다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int N, max=0, min=0x7fffffff;

int findOddCnt(char* c, int size) {
	int odd = 0;
	for (int i = 0; i < size; i++)
		if ((c[i] - '0') % 2 != 0) odd++;
	return odd;
}

//최솟값을 구함
void func(int n, int cnt) {
	int size = 1, _ = n, n2, odd = 0; 
	while (_ / 10 != 0) { //자릿수구하기
		size++;
		_ /= 10;
	}
	char c[10];
	sprintf(c, "%d", n); //문자열로 변환
	//1단계 : 각자리 숫자중 홀수 갯수를 저장
	odd += findOddCnt(c, size);

	//2단계 : 한자리면 종료 : 유일한 종료조건.
	//이곳에서 모든 최대 최소 연산이 이루어짐
	if (size == 1) {
		if (max < cnt + odd) max = cnt + odd;
		if (min > cnt + odd) min = cnt + odd;
		return;
	}

	//3단계 : 두자리면
	if (size == 2)
		func((c[0] - '0') + (c[1] - '0'), cnt + odd);

	//4단계 세자리이상이면
	if (size >= 3) {
		for (int i = 1; i < size - 1; i++) {
			for (int j = i + 1; j < size; j++) {
				int s1=0, s2=0, s3=0;
				char c1[10] = {'\0',}, c2[10] = { '\0', }, c3[10] = { '\0', };
				//3등분으로 자름
				for (int k = 0; k < i; k++) { 
					c1[s1] = c[k];
					s1++;
				}
				for (int k = i; k < j; k++) {
					c2[s2] = c[k];
					s2++;
				}
				for (int k = j; k < size; k++) {
					c3[s3] = c[k];
					s3++;
				}
				//정수로 변환
				n2 = atoi(c1) + atoi(c2) + atoi(c3);

				func(n2, cnt + odd);
			}
		}
	}
}

int main(void) {
	scanf("%d", &N);

	func(N, 0);
	printf("%d %d", min, max);

	return 0;
}