[Python/파이썬] 백준 25369번 카드 숫자 곱을 최소로 만들기

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

코드

n = int(input())
my_cards = list(map(int, input().split()))


def multiply(arr):
    if not arr:
        return 0
    result = 1
    for a in arr:
        result *= a
    return result


my_cards_mul = multiply(my_cards)


def bt(cnt, selected):
    if cnt == n:
        if multiply(selected) > my_cards_mul:
            print(*selected)
            exit(0)
        return
    for i in range(1, 10):
        bt(cnt+1, selected+[i])


bt(0, [])
print(-1)

 

multiply()

인자로 받은 배열들의 원소를 모두 곱한 결과를 리턴하는 함수이다. 만약 인자로 받은 배열이 빈 배열이라면 0을 리턴한다.

 

bt()

백트래킹을 이용하여 문제의 조건을 만족하는 해를 찾는다.

selected에 n개를 선택했을 때 내가 선택한 카드들의 곱보다 selected의 원소들을 모두 곱한 값이 더 큰 경우 중에 가장 먼저 나오는 것을 출력하고 프로그램을 종료시켜버리면 된다. 왜냐하면 우리는 작은 값들부터 넣어서 n개의 원소를 가진 selected를 만드는 과정을 반복하고 있기 때문이다.

쉽게 말하자면, n이 3이라면 [1, 1, 1], [1, 1, 2], [1, 1, 3], ... 이런 순서로 n개의 원소를 가진 selected가 완성되기 때문에 이 중 가장 먼저 문제의 조건을 만족하도록 만들어진 selected가 원소를 오름차순 정렬하여 이어붙인 수가 가장 작은 경우라는 것이다.