홀수 홀릭 호석(백준 20164번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 홀수 홀릭에 빠진 호석이는 가지고 있는 수 N을 일련의 연산을 거치면서, 등장하는 숫자들에서 홀수를 최대한 많이 많이 보고 싶다.

하나의 수가 주어졌을 때 호석이는 한 번의 연산에서 다음과 같은 순서를 거친다.

• 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.
• 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다.
• 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.
• 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각한다.

호석이는 연산이 종료된 순간에 종이에 적힌 수들을 모두 더한다. 그렇게 최종적으로 얻은 수를 최종값이라고 하자. 예를 들어, 시작하는 수가 82019 라고 하자. 그럼 아래와 같이 나누게 되면 5개의 홀수를 볼 수 있기 때문에, 최종값이 5가 된다.

https://imgur.com/gallery/a517nMU

시작할 때 호석이가 가진 수를 N 이라고 했을 때, 만들 수 있는 최종값 중 최솟값과 최댓값을 구해주자.

나의 풀이(정답 참고)

def solve(num,count):
    global max_num,min_num
    length=len(num)
    for n in num:
        if int(n)%2==1:
            count+=1
    if length>2:
        for i in range(1,length-1):
            for j in range(i+1,length):
                solve(str(int(num[:i])+int(num[i:j])+int(num[j:])),count)
    elif length>1:
        solve(str(int(num[0])+int(num[1])),count)
    else:
        max_num=max(max_num,count)
        min_num=min(min_num,count)

N=input()
min_num=10000000000
max_num=-1

solve(N,0)
print(min_num,max_num)
        

• 위 문제는 재귀함수를 사용해서 푸는 문제였다. 완전탐색(브루트 포스)으로 값을 구하는데, 이 때 숫자가 나누어지는 구간을 각 경우의 수마다 계산하여 크기를 비교한다.

+) math.inf는 무한대의 숫자를 의미. 따라서 min_num=math.inf, max_num=-math.inf를 하면 더 확실할 것 같다.