[Python] 백준 20164 - 홀수 홀릭 호석 문제 풀이

Overview

BOJ 20164번 홀수 홀릭 호석 Python 문제 풀이
분류: Implementation (구현)

---

문제 페이지

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

---

풀이 코드

from sys import stdin, maxsize


res = [maxsize, -maxsize]


def count_odds(x: str) -> int:
    cnt = 0
    for char in x:
        if char in '13579':
            cnt += 1
    return cnt


def cal(x: str, cur: int) -> None:
    if len(x) == 1:
        res[0] = min(count_odds(x) + cur, res[0])
        res[1] = max(count_odds(x) + cur, res[1])
        return

    elif len(x) == 2:
        cal(str(int(x[0]) + int(x[1])), cur + count_odds(x))

    else:
        odds = count_odds(x)
        for i in range(1, len(x) - 1):
            for j in range(i + 1, len(x)):
                cal(str(int(x[:i]) + int(x[i:j]) + int(x[j:])), cur + odds)


def main():
    x = stdin.readline().rstrip()
    cal(x, 0)
    print(*res, sep=' ')


if __name__ == "__main__":
    main()

숫자 길이에 따라 재귀적으로 연산을 진행하며, 홀수 갯수를 더해간다. 숫자 길이가 1일 되었을 때, 누적된 홀수 개수가 최소 또는 최대이면 결과값 res를 업데이트한다.

연산 과정에서 숫자 길이가 3이상인 경우에는 임의로 3등분을 해야 한다. 3등분 할 수 있는 모든 경우의 수에 대하여 연산을 수행한다.