[프로그래머스-42895 ] N으로 표현 🔑

❓ Problem

아래와 같이 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 함수를 작성하세요.

🤔 How

DP 카테고리 문제지만 DP를 어떻게 적용해하는지몰라 다른분의 풀이를 참고하여 이해한 문제 (다음에 다시 풀어봐야겠다.)

DP테이블의 접근은 숫자를 N번썻을때 어떤수를 만들수 있는가? 이다.
즉 DP[i] 일때 N 을 i 번사용해서 만들수 있는수를 DP[i] 에 보관하고 각 수를 조합하여 만들수 있는지 추적한다.

🚧 제한

• N은 최대 8번 사용 할 수 있다. 초과하는경우 -1 을 반환해야한다.

📃 생각해야할것들

• N을 사용 하여 사칙연산을 통해 만들수 있는것은 +,-,*,/ 의 경우가있다.
• 나누기의경우 divide zero 문제를 일으킬 수 있으니 이부분에대해서 처리해주어야한다.

❗ Solve

# N으로 표현


def plus_case(a, b):
    return a + b


def minus_case(a, b):
    return a - b


def multiple_case(a, b):
    return a * b


def divide_case(a, b):
    return 0 if b == 0 or a // b != a / b else a // b


def solution(N, number):
    dp = [[] for _ in range(9)]  # 최대 8개
    for i in range(1, len(dp)):
        tmp_comb = set()
        tmp_comb.add(int(str(N) * i))
        for j in range(1, i):
            for v1 in dp[i - j]:  # set
                for v2 in dp[j]:  # set
                    numbers = (v1, v2)
                    tmp_comb.add(plus_case(*numbers))
                    tmp_comb.add(minus_case(*numbers))
                    tmp_comb.add(multiple_case(*numbers))
                    if div_case := divide_case(*numbers):
                        tmp_comb.add(div_case)
        if number in tmp_comb:
            return i
        dp[i] = tmp_comb
    return -1