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

Boo Sung Jun·2022년 3월 11일
1

알고리즘, SQL

목록 보기
35/70
post-thumbnail

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등분 할 수 있는 모든 경우의 수에 대하여 연산을 수행한다.

0개의 댓글