백준[20164] 홀수 홀릭 호석

문제 풀이

문제 링크

http://icpc.me/20164

풀이

전탐색을 하여 풀 수 있다.

처음에 N조건이 10억으로 매우 크기 때문에 전탐색을 생각하기 쉽지 않지만, 이 문제는 n의 자릿수만 중요한 문제이기 때문에, 분할하는 경우가 한 번당 10^2밖에 되지 않는다. 최대 몇 번 쪼갤 수 있을지는 아무리 크게 잡아봤자 10번 미만일 것 같은 직감이 들기 때문에 O(10^3) 보다 작은 시간 안에 풀 수 있다는 믿음을 가지고 풀었다.

cf) n & 1의 값이 1이라면 n은 홀수이다. 홀수는 항상 첫번째 비트가 1이고 짝수는 0이기 때문에 이처럼 계산할 수 있다. 

코드

#include <cstdio>
#include <algorithm>

using namespace std;

int m = 1e9, M = -1e9;

void solve(int n, int cnt) {
    if (n < 10) {
        if (n & 1) cnt++;
        m = min(m, cnt);
        M = max(M, cnt);
        return;
    }
    // 각 자리수의 홀수 개수 세는 부분
    int tmp = n;
    while (tmp) {
        if ((tmp % 10) & 1) cnt++;
        tmp /= 10;
    }
    if (n < 100) {
        solve(n / 10 + n % 10, cnt);
    } else {
        for (int i = 10; i < n; i *= 10) {
            for (int j = i * 10; j <= n; j *= 10) {
            	// 수를 3등분으로 쪼개기
                int a = n % i, b = (n / i) % (j / i), c = n / j;
                solve(a + b + c , cnt);
            }
        }
    }
}

int main() {
    int n; scanf("%d", &n);
    solve(n, 0);
    printf("%d %d", m, M);
}