백준 20164 홀수 홀릭 호석 혼내주기

 

제 1회 류호석배 알고리즘 코딩 테스트 문제.

 

실시간으로 제 2회 류호석배 알고리즘 코딩 테스트 진행중이다. 실전 느낌으로 도전했는데, 1솔에 1문제는 일부분만 맞고 (사실상 틀린것) 나머지는 생각해봐도 방법이 떠오르지 않아서 깔끔하게 포기하고 1회 문제들을 풀고 있다.

 

 

 

(오답주의)

#include <iostream>
#include <vector>
using namespace std;

int ie[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

int countOdd(int n){
    int ret = 0;
    while(n >= 10){
        if(n%2 == 1) ret++;
        n /= 10;
    }
    if(n%2 == 1) ret++;
    return ret;
}

int countDigits(int n){
    int ret = 1;
    while(n >= 10){
        n /= 10;
        ret++;
    }
    return ret;
}

pair<int, int> odd(int n){
    
    int digits = countDigits(n);
    if(digits == 1) return {countOdd(n), countOdd(n)};
    if(digits == 2) return {countOdd(n) + countOdd(n/10 + n%10), countOdd(n) + countOdd(n/10 + n%10)};
    
    int mx = 0, mn = 1e9;
    pair<int, int> ret = {mx, mn};
    for(int i = 0; i < digits-2; ++i){
        for(int j = i+1; j < digits-1; ++j){
            int prev =  n / ie[(digits-1) - i];
            int next = n % ie[(digits-1) - j];
            int mid = (n - prev*ie[(digits-1) - i]) / ie[(digits-1) - j];
            
            pair<int, int> tmp = odd(prev + mid + next);
            ret.first = max(ret.first, tmp.first);
            ret.second = min(ret.second, tmp.second);
        }
    }

    return {ret.first + countOdd(n), ret.second + countOdd(n)};

}

int main(){
    int n;
    cin >> n;
    pair<int, int> ans = odd(n);
    cout << ans.second << " " << ans.first;
}

 

처음에 문제를 보고 어떻게 풀어야 하는지 감이 와서 위와 같이 구현했는데 계속 몇몇 케이스를 통과하지 못했다. 그래서 풀이를 보고 최소 최대값을 리턴하는 방식에서 전역변수에 업데이트 하는 방식으로 바꾸니 통과했다. 솔직히 아직도 왜 내 코드가 틀렸는지 잘 모르겠다... 아시는 분 있으면 댓글 부탁드립니다(꾸벅).

 

 

그리고 나는 구데기같이 복잡하게 자리수를 계산해서 풀었는데, 풀이를 보니 문자열로 깔끔하게 처리해서 보고 배웠다. 처음에 문자열로 처리하면 편하겠다는 생각을 하다가 뭐 때문에 안될 것 같아서 자리수로 했는데, 다음부턴 될지 안될지를 확실하게 구분해서 접근해야겠다.

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int mx = 0, mn = 1e9;

int countOdd(int n){
    int ret = 0;
    while(n >= 10){
        if(n%2 == 1) ret++;
        n /= 10;
    }
    if(n%2 == 1) ret++;
    return ret;
}

void odd(int n, int cnt){

    if(n < 10){
        mx = max(mx, cnt);
        mn = min(mn, cnt);
        return ;
    }
    if(n < 100) {
        int num = n/10 + n%10;
        odd(num, cnt + countOdd(num));
        return ;
    }
    
    string s = to_string(n);
    for(int i = 1; i < s.length()-1; ++i){
        for(int j = i+1; j < s.length(); ++j){
            string s1 = s.substr(0, i);
            string s2 = s.substr(i, j-i);
            string s3 = s.substr(j, s.length() - j);
            int num = stoi(s1) + stoi(s2) + stoi(s3);
            odd(num, cnt + countOdd(num));
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    odd(n, countOdd(n));
    cout << mn << " " << mx;
}