def solution(N, number):
    if N == number:
        return 1

    # dp[i]: N을 i번 사용해서 만들 수 있는 수 집합
    dp = [{int(str(N) * i)} for i in range(1, 9)]
    dp.insert(0, set())  # dp[0]은 사용하지 않음(인덱스 헷갈려서 공간낭비 하나 함)

    for i in range(1, 9):
        for j in range(i):
            # num1: N을 j번 사용해서 만들 수 있는 수
            # num2: N을 N-i번 사용해서 만들 수 있는 수
            for num1 in dp[j]:
                for num2 in dp[i - j]:
                    dp[i].update([num1 + num2, num1 - num2, num1 * num2])
                    if num2 != 0:
                        dp[i].add(num1 // num2)

        # N을 i번 사용해서 만들 수 있는 수가 dp[i]에 모두 만들어짐
        if number in dp[i]:
            return i

    return -1


assert (solution(5, 12) == 4)
assert (solution(2, 11) == 3)
