N으로 표현

문제설명

아래와 같이 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 합니다.

 

 

---

입출력 예

---

입출력 예에 대한 설명

---

풀이

혼자 생각하다 풀지 못해 다른 사람들의 풀이를 참고해 이해한 뒤 다시 구현하였다. 원리는 이러하다. N으로 number를 나타낼 때 '몇 개의 N을 써야 하는지'가 최종적으로 출력해야 하는 답이다. 근데 8이 넘어가면 -1을 출력한다. N을 3개 써야하는 경우는 어떻게 구할 수 있을까? 바로 N을 1개 사용하는 경우와 2개 사용하는 경우끼리 사칙연산을 통해 구할 수 있다. 이러한 원리에 착안해 S=[]라는 집합을 만들고 S=[{N}, {NN}, {NNN}, ..., {NNNNNNNN}]로 구성한다. {NN}은 N을 2개 사용하여 만들 수 있는 수들의 집합이다.

아 참고로 N==number인 경우를 먼저 검사해야 한다. 안그러면 최솟값을 출력하지 못하는 경우가 있다. 간혹, op1-op2에서 op2-op1으로 해야할지 순서가 헷갈려하는 경우가 있다. 그런데 한 가지만 쓰면 괜찮은 이유가 for문을 통해 결국 순서가 바뀌어 다 순회하기 때문이다. 예를 들어, N 3개로 표현하는 경우를 구할 때 3=1+2=2+1이므로 for문을 돌면서 {N}, {NN}순으로 적용했던 사칙연산이 나중엔 {NN},{N}순으로 적용되기 때문에 괜찮다는 것이다.

동적프로그래밍을 이런 식으로 적용할 수도 있다는게 좀 놀랍다...새로운 방법이다.

def solution(N, number):
    if N==number:
        return 1
    answer = -1
    S = [set() for _ in range(8)]
    for i in range(8):
        S[i].add(int(str(N)*(i+1)))
    for i in range(1, len(S)):
        for j in range(i):
            for op1 in S[j]:
                for op2 in S[i-j-1]:
                    S[i].add(op1+op2)
                    S[i].add(op1-op2)
                    S[i].add(op1*op2)
                    if op2!=0:
                        S[i].add(op1//op2)
        if number in S[i]:
            answer=i+1
            break
            
    return answer