[C++] 백준 20166번: 홀수 홀릭 호석 - Recursion

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

20164번: 홀수 홀릭 호석

 

1 ~ 10^9 - 1 범위의 정수 N이 주어지면, N을 잘 분해하여 홀수의 개수를 구하는 문제이다.

당연히 N의 길이가 1인 경우와 2인 경우, 3 이상인 경우를 나누어 생각했고,

1인 경우와 2인 경우는 쉬우나 3 이상인 경우에는 N을 쪼갤 수 있는 모든 방법으로 쪼갠 결과를 저장해야했으므로

3 이상인 경우를 생각해보았다.

 

먼저 예제로 주어진 82019를 보면

8 / 2 / 019 => 29

8 / 20 / 19 => 47

8 / 201 / 9 => 218

82 / 0 / 19 => 101

82 / 01 / 9 => 92

820 / 1 / 9 => 830

이렇게 6가지의 경우가 나오는데, 이를 위해 substring 함수를 사용해서 반복문을 돌려 분할해주었다.

여기서 더해진 값이 다시 3 이상인 경우가 될 수도 있으니 이를 다시 재귀적으로 풀어주어야했다.

 

 

#include <iostream>
#include <string>
using namespace std;
int mi=2147483647, ma;
void back(string s, int ans){
    string a, b, c;
    if(s.length()==1){
        if((s[0]-'0')%2) ans++;
        mi=min(mi, ans);
        ma=max(ma, ans);
        return;
    }
    else if(s.length()==2){
        if((s[0]-'0')%2) ans++;
        if((s[1]-'0')%2) ans++;
        s=to_string(s[0]-'0'+s[1]-'0');
        back(s, ans);
    }
    else{
        int cnt=stoi(s);
        while(cnt!=0){
            if(cnt%2) ans++;
            cnt/=10;
        }
        for(int i=1; i<s.length()-1; i++){
            for(int j=1; j<s.length()-i; j++){
                a=s.substr(0,i);
                b=s.substr(i,j);
                c=s.substr(i+j,s.length());
                cnt=stoi(a)+stoi(b)+stoi(c);
                back(to_string(cnt), ans);
            }
        }
    }
}
int main(){
    string s; cin >> s;
    back(s, 0);
    cout << mi << " " << ma;
}