백준 : 20164 - 홀수 홀릭 호석

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

흠,,, 문제는 막 어렵진 않았던것같다

그냥 냅다 잘라서 홀수찾음 되는 문제였다.

시간은 0ms니까 나쁘지 않은것같은데 메모리가 다른사람보다 좀 많다.ㅠㅠ

---

재귀를 여러번 반복해서 해결했다.

tree형태로 내려간다고 생각했을 때

대충 이런느낌을 생각할 수 있다.

(왼쪽이 숫자, 오른쪽이 홀수개수)

1. 숫자의 길이가 2개이거나, 1개일때 다음 경우의 수는 1개로 고정된다 (child 한개뿐)

2. 숫자의 길이가 3개이상일때, 경우의 수가 여러개 생긴다 (size-1 C 2 의 경우의수를 가짐)

=> 생기는 여러 경우의 수마다, odd개수를 각각 가지고, 이 중 최소, 최대만 뽑아서 생각하면 된다

 

그래서 재귀할 때 return을 {max, min} vector형태로 주었다!

#include<iostream>
#include<vector>
#include<cmath>
#include<string>

using namespace std;

vector<int> split(int number){
    // {max, min} 형태로 리턴해주기
    int size = log10(number) + 1;
    if(size == 1){
        // 종료
        //cout << "size == 1 : "<<number<<", ";
        if((number%2) == 0){
            // 짝수
            //cout << "{0,0}"<<endl;
            return {0,0};
        }else{
            // 홀수
            //cout << "{1,1}"<<endl;
            return {1,1};
        }
        
    }else if(size == 2){
        // 두개로 나누기
        //cout << "size == 2 : "<<number<<", ";
        int odds = 0;
        int a = number/10;
        if((a%2) != 0){
            odds++;
        }
        int b = number%10;
        if((b%2) != 0){
            odds++;
        }
        int next = a + b;
        //cout << "a : "<<a<<", b : "<<b<<endl;
        odds += split(next)[0]; // 무조건 2자리숫자여서 [0], [1] 이 같음
        return {odds, odds};
    }

    //cout << "size == 3 : "<<number<<endl;

    int odds = 0;
    int iternum = number;
    vector<int> numbers;
    for(int i = size-1; i>=0; i--){
        int temp = iternum/pow(10,i);
        if((temp%2) != 0){
            odds++;
        }
        numbers.push_back(temp);
        iternum -= temp * pow(10, i);
    }

    // 3개로 나누기
    // -> 여러가지 경우가 있음
    // 숫자를 [size번째 자릿수], [size-1 번째], .... , [1번째] 모양으로 보면
    int max = 0;
    int min = 11;
    for(int i = size; i>=3; i--){
        // 첫번째 숫자가 끝나는 지점
        // [1자릿수] ~ [i번째 자릿수]
        for(int j = i-1; j>=2; j--){
            // 두번째 숫자가 끝나는 지점
            // [i-1번째 자릿수] ~ [j번째 자릿수]
            
            // 세번째 숫자는 자동으로 결정
            // [j-1번째 자릿수] ~ [1 번째 자릿수]

            int num1 = number / pow(10, i-1);
            int temp = number-(num1*(pow(10, i-1)));
            int num2 = temp / pow(10, j-1);
            int num3 = temp - (num2 * (pow(10, j-1)));

            vector<int> next = split(num1 + num2 + num3);
            if(next[0] > max){
                max = next[0];
            }
            if(next[1] < min){
                min = next[1];
            }
        }
    }
    return {max + odds, min + odds};
}


int main(){

    int n;
    cin >> n;

    vector<int> answer = split(n);

    cout << answer[1] << " "<<answer[0]<<endl;


    return 0;
}

---

메모리 사용량이 많은이유,,,

일단 중간에 숫자를 vector로 굳이 바꿀필요 없었다 (뒤에서 사용안함)

push_back도 필요가 없었고..

오 이거때문에 메모리 사용량이 많아진것 같기도 하다! 아닌가? 아무튼..

 

맞았으니까 됐어~