[プログラマLV 3]N表示


1.問題の説明
Nと表示
2.問題分析
現段階の解決策は後段階で使用する問題である.四則演算では、和と乗の順序は関係ありませんが、マイナス記号と除算記号の値は順序によって変化することに注意してください.重複する数字を消すためにsetを使用しました.
i回使用
  • Nは、生成(四則演算Xを使用)および(四則演算Oを使用)することができる.電子は簡単にN個のi号を列挙すればよい.
  • 四則演算を使用する場合、N(1,2,...,i-1)回に生成された数値リストを使用します.
  • N作成に4回の使用が必要な数量、
  • N을 4번 사용해야 하는 경우 = 
    (1). (N을 1번 사용해 만든 수들) +-*/ (N을 3번 사용해 만든 수들) 
    (2). (N을 2번 사용해 만든 수들) +-*/ (N을 2번 사용해 만든 수들)
    すなわち、上記のように既に前のi回よりも小さい場合には、「求められた」dpにより現在のi回で利用可能な数を求めるべきである.
    3.私の回答
    def calculator(j, k):
        tmp = []
        tmp.append(j+k)
        tmp.append(j*k)
        tmp.append(j-k)
        tmp.append(k-j)
        if k != 0: tmp.append(j//k)
        if j != 0: tmp.append(k//j)
        return tmp
    
    def solution(N, number):
        dp = [[0]]
        # dp[n] -> n개의 N을 사용했을 때 만들어지는 수를 담은 배열
        for i in range(1, 9):
            tmp = set()
            base = int(str(N)*i)
            tmp.add(base)
            # 사칙연산 사용 X
    
            for idx in range(1, i):
                for j in dp[idx]:
                    for k in dp[i-idx]:
                        # N을 2개 쓴 경우 -> 1개 쓴 경우를 두 번 활용
                        # N을 3개 쓴 경우 -> 1개 쓴 경우 + 2개 쓴 경우 활용
                        # N을 4개 쓴 경우 -> 1개 쓴 경우 + 3개 쓴 경우 활용 / 2개 쓴 경우 + 2개 쓴 경우
                        #... N을 i개 쓴 경우 -> idx개 쓴 경우 + (i-idx)개 쓴 경우
                        for item in calculator(j, k):
                            tmp.add(item)
                            # 집합 tmp는 j와 k를 활용한 모든 사칙연산 결과를 포함 -> 중복값 제거
            if number in tmp:
                return i
            # N을 i개 쓴 tmp 차례에서 number 발견
            tmp = list(tmp)
            dp.append(tmp)
    
        return -1