문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.

풀이

def solution(N, number):
    answer = -1
    if number == N:
        return 1
    s = [set() for _ in range(8)]  # s[n] 은 n+1개로 만들 수 있는 수의 집합
    for i in range(8):
        temp = int(str(N)*(i+1))
        s[i].add(temp)

    for i in range(1, 8):  # i는 1~7 까지 순회 -> 계산된 수를 집어 넣을 인덱스
        for j in range(i):  # j는 i 만큼 순회
            for x1 in s[j]:  # j+1개로 만들수 있는 조합들을 하나씩 꺼냄
                # i-j-1 -> i(들어갈 인덱스) - j(x1의 인덱스) -1(인덱스가 0부터 시작하므로)
                for x2 in s[i-j-1]:
                    s[i].add(x1 + x2)
                    s[i].add(x1 - x2)
                    s[i].add(x1 * x2)
                    if x2 != 0:
                        s[i].add(x1 // x2)
        if number in s[i]:
            return i+1
    return answer

• 8개의 집합 리스트 s를 만든다
• s[k]는 k+1개로 만들 수 있는 수의 집합이다
• 각각을 N으로 채워 넣는다. N=5라면
• s = [{5},{55},{555},{5555},{55555},{555555},{5555555},{55555555}] 가 된다.
• i는 사칙연산의 결과를 집어 넣을 집합의 인덱스다. 1~7 순회
• j는 x1의 인덱스다. 0~i순회
• i-j-1은 x2의 인덱스다.

  ex) i=5, j=3
  우리가 원하는건 6개의 N으로 만들수 있는 조합이다(s[5]의 원소).
  j가 3일때 x1은 4개의 N으로 만들 수 있는 수(s[3]의 원소)이므로 x2는 2개(6-4)로 만들 수 있는 수(s[1]의 원소)여야한다. 따라서 -1을 해줘야 함 (i-j-1 인 이유)

• x1과 x2의 사칙연산의 결과를 전부 s[i]에다 집어넣은 후
• s[i]안에 number가 있으면 i+1을 리턴해준다
• for문을 빠져나가면 8개 이상이므로 -1을 리턴
• 3으로 3만들기 같은 예외처리(무조건 1 리턴하게) 해줘야한다.