[백준,c++] 20164번 - 홀수 홀리 호석

문제

20164번: 홀수 홀릭 호석

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int max_v = -1, min_v = 1e9+1;

void backtraking(string s, int cnt){
    for(char c : s){
        if((c-'0')&1) cnt++;    // 홀수 갯수 카운팅
    }
    if(s.length() == 1){
        max_v = max(max_v , cnt);
        min_v = min(min_v, cnt);
        return;
    }
    if(s.length() == 2){
        backtraking(to_string(s.front()- '0' + s.back() - '0'), cnt); // 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.
    }
    if(s.length()>=3){
        for(int i=1; i<s.length(); i++){
            for(int k= i+1; k<s.length(); k++){
                string a = s.substr(0, i);
                string b = s.substr(i, k-i);
                string c = s.substr(i + k - i, s.length() - k);
                if(a == "") a = "0";
                if(b == "") b = "0";
                if(c == "") c = "0";
                backtraking(to_string(stoi(a) + stoi(b) + stoi(c)), cnt);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string s; cin>>s;
    
    backtraking(s, 0);
    
    cout<<min_v<<' ' << max_v;
}

 

풀이

문제의 풀이 조건 중 다음 조건을 처리하기가 까다로웠습니다.

수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각한다.

임의의 위치에서 끊어서 3개의 수로 분할해야 하는데, 해당 방법은 다음 로직과 같습니다.

for(int i=1; i<s.length(); i++){
            for(int k= i+1; k<s.length(); k++){
                string a = s.substr(0, i);
                string b = s.substr(i, k-i);
                string c = s.substr(i + k - i, s.length() - k);
                if(a == "") a = "0";
                if(b == "") b = "0";
                if(c == "") c = "0";
                backtraking(to_string(stoi(a) + stoi(b) + stoi(c)), cnt);
            }
        }

위 조건만 구현한다면 크게 문제없는 문제였습니다.