(20164호) 오드홀릭 넘버틴

질문

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

해결책

(질문)

• 숫자가 주어지면 Hosen은 하나의 계산에서 다음 순서로 진행합니다.
  
  
  • 종이에 각 숫자의 홀수 개수를 적으세요.
  • 숫자가 한 자리이면 아무 작업도 수행하지 않고 종료됩니다.
    
    
  • 숫자가 2자리일 경우 2로 나누어 합을 구하여 새로운 숫자로 취급합니다.
    
    
  • 숫자가 3자리 이상일 경우 임의의 위치에서 잘려서 3개의 숫자로 나누어 세 숫자의 합을 새로운 숫자로 간주한다.
    
    
• 이런 식으로 1회 연산 후 기록된 숫자를 모두 더해 새로운 숫자를 얻고 계속해서 연산을 하며 각 연산에서 홀수의 개수를 센다.
  
  (최소 최대)

(해결하다)

• 재귀적 사용
  • 연산을 수행한 후 문자열 값과 지금까지 발생한 정수의 홀수를 매개변수로 받습니다.
    
    
  • 현재 전달된 문자열을 3자리 이상, 2자리 또는 1자리로 분할하여 문제를 해결합니다.
    
    
  • 문자열이 3자리를 초과하면 가능한 모든 분할 가능한 상황을 고려하여 문자열을 나누고, int로 변환하고, 더하고, 문자열로 변환하고, 재귀적으로 호출합니다.
    
    
  • 문자열이 2자리인 경우 위와 동일합니다.
    
    
  • 문자열이 1비트이면 종료 조건입니다.
    
    -> 최소값과 최대값을 업데이트하고 재귀를 종료합니다.
    
    

(암호)

#include <iostream>
#include <string>

using namespace std;

string N;
int min_value = 987654321;
int max_value;
int ans;

// string이 주어졌을 때, 홀수 개수 찾는 method
int findEvenCnt(string s){
    int cnt = 0;
    for(int i=0; i<s.size(); i++){
        if((s(i) - '0') % 2 !
= 0) cnt++;
    }
    return cnt;
}

void calculate(string n, int ans){ // n: 연산 이후 다 더해진 값의 string, ans: 현재까지 나온 홀수 개수
    ans += findEvenCnt(n); // 홀수 개수 count
    
    if(n.size() >= 3){ // 세자리 이상이면 3개의 수로 분할 후 더함.
        for(int i=0; i<n.size()-2; i++){
            for(int j=1; j<n.size()-i-1; j++){
                string token1 = n.substr(0, i+1);
                string token2 = n.substr(i+1, j);
                string token3 = n.substr(i+j+1);
                int num = stoi(token1) + stoi(token2) + stoi(token3); // 3개의 string token을 다 더해서 number를 만든다.


                string s = to_string(num); // 만든 number를 다시 string으로 변환해서
                calculate(s, ans); // 재귀호출
            }
        }
        
    }
    if(n.size() == 2){ // 두개로 나눠서 더함. 세자리 이상인 경우와 로직 동일.
        string token1 = n.substr(0, 1);
        string token2 = n.substr(1, 1);
        int num = stoi(token1) + stoi(token2);
        string s = to_string(num);
        calculate(s, ans);
    }
    
    if(n.size() == 1){ // string size가 1인 경우는 min, max 갱신 후 재귀 종료.
        if(min_value > ans){
            min_value = ans;
        }
        if(max_value < ans){
            max_value = ans;
        }
        return;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // Input
    cin >> N;
    
    // Solution
    calculate(N, 0);
    
    // Answer
    cout << min_value << ' ' << max_value;
    
    
    return 0;
}

(경고하다)

문자열 길이가 3보다 크면 적절한 구문 분석으로 쉽게 해결할 수 있습니다.

구문 분석 부분에 주의하십시오.