[C/C++] 백준 - 20164번(홀수 홀릭 호석)

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

20164번: 홀수 홀릭 호석

문제

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

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

• 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.
• 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다.
• 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.
• 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각한다.

호석이는 연산이 종료된 순간에 종이에 적힌 수들을 모두 더한다. 그렇게 최종적으로 얻은 수를 최종값이라고 하자. 예를 들어, 시작하는 수가 82019 라고 하자. 그럼 아래와 같이 나누게 되면 5개의 홀수를 볼 수 있기 때문에, 최종값이 5가 된다.

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 109-1, N 은 자연수이다.

---

처음 문제를 읽고 잘 못 이해해서 상당히 시간을 날린 문제이다.
구현 문제라서 각 구현 목록을 나눠준 후 구현만 해주면 된다.

1) 숫자의 길이가 1인 경우는 끝
2) 숫자의 길이가 2일 때는 각 자리수 값을 더해준다.
3) 숫자의 길이가 3 이상 일 때는 숫자를 나눌 수 있는 모든 3조각으로 나눠준 후 하나의 값으로 합쳐주는 과정을 진행해준다. 이 과정을 진행하기 위해 재귀함수를 구현하였으며 1)번이 나올 경우까지 재귀함수로 진행해주면 된다.

나는 처음에 3조각이 아닌 나눌 수 있는 모든 조각으로 나누기 위해 조합을 구현하려하였다. 문제를 제대로 파악하지 못한채 문제가 이상하다고 생각하였고 삽질을 한 것. 아무리 생각해도 말이 안돼서 다시 문제를 바로 읽고 빠르게 오류를 잡아주었다.

3조각으로만 나눠주면 되기 때문에 굳이 조합으로 구현 할 필요 없이 for문 2개로 간단하게 나눠줄 수 있다.

for(int i=1;i<n.length()-1;i++){
    for(int j=i+1;j<n.length();j++){
    	string s1 = n.substr(0, i);
	string s2 = n.substr(i, j-i);
	string s3 = n.substr(j, n.length()-j);

	int sum = getSum(s1, s2, s3);
	string temp = to_string(sum);
	int count = getOddNumber(temp);

	func(temp, cnt+count);
	}
}

위 처럼 그냥 바로 슬라이싱 해줘서 모든 3조각으로 나눠주기만 하면 된다.

그리고 재귀함수이기에 계속해서 반복적으로 진행하는 코드가 분명히 존재한다.
나는 이러한 부분을 함수로 따로 빼줘서 구현하는 방식으로 택하였다.

1) 숫자를 문자열로 변환한 후 각 자리수가 홀수인지 확인하고 총 홀수의 개수를 반환하는 함수 구현
2) 3조각으로 나눈 문자열들을 정수로 변환한 후 각 값들을 모두 합한 값을 반환하는 함수 구현

간단하게 위와 같은 2가지 함수루 나눠 구현해주었다.

이렇게 해야 각 중복되는 코드도 줄일 수 있을 뿐 아니라, 같은 기능은 같은 코드로 돌아가게 되어 수정이 필요할 때 함수 하나만 수정해주면 된다는 장점이 있다.

아래는 전체 코드이다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 123456789
#define endl '\n'

using namespace std;

string N;
int maxV = -INF, minV = INF;

void input(){
	cin >> N;
}

int countingInitNumber(){
	int cnt = 0;
	for(int i=0;i<N.size();i++){
		if((N[i] - '0') % 2 != 0) cnt++;
	}
	return cnt;
}

int getOddNumber(string temp){
	int count = 0;
	for(int i=0;i<temp.size();i++){
		if((temp[i] % 2 != 0)) {
			count++;
		}
	}
	return count;
}

int getSum(string s1, string s2, string s3){
	return stoi(s1) + stoi(s2) + stoi(s3);
}

void func(string n, int cnt){
	if(n.size() == 1){
		maxV = max(maxV, cnt);
		minV = min(minV, cnt);
		return;
	}

	if(n.size() == 2){
		string temp = to_string((n[0]-'0') + (n[1]-'0'));
		int count = getOddNumber(temp);
		func(temp, cnt+count);
	} else { 
		for(int i=1;i<n.length()-1;i++){
			for(int j=i+1;j<n.length();j++){
				string s1 = n.substr(0, i);
				string s2 = n.substr(i, j-i);
				string s3 = n.substr(j, n.length()-j);

				int sum = getSum(s1, s2, s3);
				string temp = to_string(sum);
				int count = getOddNumber(temp);

				func(temp, cnt+count);
			}
		}
	}
}

void solution(){
	int cnt = countingInitNumber();
	func(N, cnt);
	cout << minV << " " << maxV << endl;
}

int main() {
	fastio;
	input();
	solution();
	
	return 0;
}