백준 20164 (C++) 홀수 홀릭 호석

최초 업로드: 2025-03-16 04:28:00

최근 수정 시간: 2025-07-25 10:13:53

게시자: rlatjwls3333

카테고리: 백준

# [Gold V] 홀수 홀릭 호석

#### [문제링크](https://www.acmicpc.net/problem/20164)

## 문제 설명

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

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

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

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

## 입력

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

## 출력

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

## 풀이
#### 이 문제는 수를 2등분이나 3등분을 내서 합친 결과로부터 홀수를 본  최소/최대 횟수를 계산하는 문제입니다.
#### 수를 세는 과정에서 재귀를 이용한 가지치기로 보지 않아도 되는 무의미한 결과를 무시하여 시간을 단축할 수 있습니다.
#### 수를 문자열로 받는다면 아무리 길어봐야 9자리이기 때문에 문자열을 3등분을 계속 내는 최악의 경우에도 시간 초과는 나지 않습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

pair<int, int> cut(string s) { // {최소횟수, 최대횟수}로 return
 int cnt=0;
 for(int i=0;i<s.length();i++) {
 cnt += (s[i]-'0')%2; // 홀수의 개수 세기
 }

int minCnt = INT_MAX, maxCnt = 0;
 if(s.length()==1) {
 // 길이가 1인 경우 더 자를 수 없음
 minCnt = maxCnt = cnt;
 } else if(s.length()==2) {
 // 길이가 2면 반으로 자르고 개수 세기
 auto ret = cut(to_string(s[0]+s[1]-'0'*2));
 minCnt = cnt+ret.first;
 maxCnt = cnt+ret.second;
 } else {
 // 길이가 3 이상이면 다 잘라서 최솟값, 최대값 확인
 for(int i=1;i<s.length();i++) {
 for(int j=i+1;j<s.length();j++) {
 string a = s.substr(0, i);
 string b = s.substr(i, j-i);
 string c = s.substr(j, s.length()-j);
 
 auto ret = cut(to_string(stoi(a) + stoi(b) + stoi(c)));
 minCnt = min(minCnt, ret.first+cnt);
 maxCnt = max(maxCnt, ret.second+cnt);
 }
 }
 }
 return {minCnt, maxCnt};
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 string s; cin >> s;
 auto ret = cut(s);
 cout << ret.first << ' ' << ret.second;
}
```