문제링크

설명 :

82019 → 홀수 2개

82 + 0 + 19 → 101 → 2개

1 + 0 + 1 = 2 → 0개

→ 최소 4

복잡도 : O(N^2)? O(N^3)?

→ 하지만 이 문제는 1 ≤ N ≤ 10^9-1, N 은 자연수이다.

라고 되어 있어서 시간 복잡도를 신경 써야 할 것 같아 보이지만

실제로는 입력된 숫자의 길이(최대 10)이기 때문에 시간 복잡도를 신경 쓸 필요가 없음

재귀를 통해 구현함

아이디어 : 시간복잡도를 신경 쓸 필요가 없기 때문에 모든 방법에 대해 비교하는 브루트포스식 구현을 하자

def old_holic_hosuk(num, count):
    ans_max = 0
    ans_min = float('inf')

    # 현재 숫자에서 홀수를 카운트
    for digit in num:
        val = int(digit)
        if val % 2 != 0:
            count += 1

    # 숫자가 1개 일 때는 그냥 리턴
    if len(num) == 1:
        ans_min = ans_max = count
        return ans_min, ans_max

    # 숫자가 2개 일 때는 두 수를 합해서 재귀함수 호출
    elif len(num) == 2:
        val = sum(int(digit) for digit in num)
        return old_holic_hosuk(str(val), count)

    # 숫자가 3개 이상일 때
    else:
        # 3등분할 수 있는 모든 경우의 수를 다 해줌
        for i in range(len(num) - 2):
            for j in range(i + 1, len(num) - 1):
                s1 = num[:i + 1]  # 0 ~ i 까지
                s2 = num[i + 1: j + 1]  # i+1 ~ j까지
                s3 = num[j + 1:]  # j ~ 끝 까지
                total = int(s1) + int(s2) + int(s3)
                # 합한 수로 다시 재귀함수 호출
                val_min, val_max = old_holic_hosuk(str(total), count)
                # 최대 최솟값을 비교, 갱신
                ans_min = min(ans_min, val_min)
                ans_max = max(ans_max, val_max)

        return ans_min, ans_max

n = input()
answer_min, answer_max = old_holic_hosuk(n, 0)
print(answer_min, answer_max)