[백준 20164번] 홀수 홀릭 호석

20164번: 홀수 홀릭 호석

# 주어진 수 N (<= 10^9)
# 최종값의 '홀수의 개수'의 최솟값과 최댓값 구하기

from itertools import combinations

n = int(input())

minimum = float("inf")
maximum = float("-inf")

def count_odd(arr): # 숫자 문자열 배열의 홀수 개수를 count하는 함수
    count = 0
    for i in arr:
        if int(i)%2 == 1:
            count += 1
    return count

def dfs(num_str,odd_count): # 종료할 때까지 재귀적으로 탐색하는 dfs함수

    global minimum
    global maximum

    current_odd_count = count_odd(num_str) # 1. 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.
    
    if len(num_str) == 1: # 2. 수가 한자리이면 더 이상 아무것도 하지 못하고 종료
        new_count = odd_count + current_odd_count
        if new_count < minimum:
            minimum = new_count
        if new_count > maximum:
            maximum = new_count
        return

    elif len(num_str) == 2: # 3. 수가 두자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각
        new_num = int(num_str[0]) + int(num_str[1])
        new_str = list(str(new_num))

        dfs(new_str, odd_count + current_odd_count)

    elif len(num_str) >= 3: # 4. 수가 세자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할 후 3개를 더한 값을 새로운 수로 생각
        index_list = [x for x in range(1,len(num_str))]

        combs = list(combinations(index_list,2))

        for first, second in combs:
            one = "".join(num_str[:first])
            two = "".join(num_str[first:second])
            three = "".join(num_str[second:])

            total = list(str(int(one) + int(two) + int(three)))
            
            dfs(total,odd_count+current_odd_count)

dfs(list(str(n)),0)

print(f"{minimum} {maximum}")

 

이번 문제는 주어진 숫자의 홀수 개수를 먼저 구한 뒤,

1. 숫자가 1자리라면 여태까지 발견한 홀수의 개수를 모두 더하여 '홀수의 총 개수의 최솟값과 최댓값'을 갱신하고

2. 숫자가 2자리라면 두 개로 나눠서 그 합을 구하여 새로운 수로 생각(재귀)하고

3. 숫자가 3자리라면 임의의 위치에서 숫자를 끊어서 3개의 수로 분할한 후 그 합을 구하여 새로운 수로 생각(재귀)하는 문제이다.

 

주어진 숫자에 따라 경우의 수를 나누고 새로운 수로 생각한다는 문구를 보고 완전 탐색(Brute Force) 문제라는 것을 확인했고, 숫자의 자리수를 쉽게 파악하기 위한 '숫자 문자열 배열(num_str)'과 '현재까지 발견한 홀수의 개수(odd_count)'를 인자로 받았다. ex) 514 👉🏻 ['5', '1', '4']

 

그 후 배열의 길이(len(num_str))에 따라 분기처리를 해주었는데, 가장 중요한 것은 자리수가 3개 이상일 때이다.

 

임의의 위치에서 숫자를 끊기 위해서는 1부터 마지막 인덱스까지 중에서 임의의 숫자 2개를 뽑아야 하기 때문에 itertools 라이브러리의 조합(combinations) 메서드를 사용하였다.

 

그렇게 구한 모든 경우의 수들에서 재귀적으로 dfs함수를 호출하여 자리수가 1개, 즉 종료될 때까지 탐색하도록 하여 최댓값과 최솟값을 갱신해주는 방식으로 풀이하였다.

 

다른 사람들의 풀이를 참고해본 결과, itertools의 combinations를 사용하지 않고 2중 반복문으로 풀이할 수 있는 것을 알 수 있었다. 완전탐색을 복습할 수 있었던 좋은 문제였다 :)