[백준] 20164번 (python 파이썬)

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

구현, 재귀 문제이다.

 

여기서 생각해야 하는 문제는 숫자가 세자리 이상일때 3등분을 해야 하는데 어떻게 해야할지 이다.

 

간단하게 모든 경우의 수를 구하여 3등분을 한다.

 

 

 

2중 반복문을 통해서 구역을 나눌수 있다.

 

분할한 구역으로 새로운 숫자를 만들어서 다시 재귀를 돌린다.

새로운 숫자가 한자리 숫자일때까지 재귀를 돌린다.

 

import math

n = input()

min_v = math.inf
max_v = 0


def command1(n: str):
    odd_n = 0
    for i in n:
        if int(i) % 2 != 0:
            odd_n += 1
    return odd_n


def solve(n, odd_n):
    global max_v, min_v

    if len(n) == 1:
        min_v = min(min_v, odd_n)
        max_v = max(max_v, odd_n)
    elif len(n) == 2:
        temp = str(int(n[0]) + int(n[1]))
        solve(temp, odd_n + command1(temp))
    else:
        for i in range(len(n) - 2):
            for j in range(i+1, len(n)-1):
                a = n[:i+1]
                b = n[i+1: j+1]
                c = n[j+1:]
                temp = str(int(a) + int(b) + int(c))
                solve(temp, odd_n + command1(temp))


solve(n, command1(n))
print(min_v, max_v)