디너코딩

문제 설명

아래와 같이 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                                                   return

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

이 문제는 스스로 몇시간동안 삽질을 해보아도 도무지 해결방안이 생각이 안나서 다른 사람의 글을 참고하였다. 참조한 블로그는 아래쪽에 써두었다. N을 8개까지 사용가능하다는 점에서 N을 1개 사용했을 때부터 차례대로 사칙연산을 해본다.

N이 1개일 때,

5

N이 1개라면 5만 만들어진다.

N이 2개일 때,

55, 5+5, 5-5, 5/5, 5*5

-> 55, 10, 0, 1, 25

N이 2개일 때는 2가지 종류가 있다.

N을 1개 덧붙이는 값 : 55

N이 1개일 때의 집합끼리 사칙연산한 값:  10, 0, 1, 25

N이 3개일 때,

N이 3개일 때는 N이 1개일 때와, 2개일 때에 대하여 사칙연산을 진행한다. 더하기 연산과 곱셈 연산은 순서가 상관이 없지만, 뺄셈 연산과 나눗셈 연산은 순서가 상관이 있으므로 반대의 경우에도 연산을 한 번 해준다.

N이 4개일 때,

4=1+3=2+2 이므로 N이 1개일 때와 3개일때 / N이 2개일 때와 2개일 때에 대하여 사칙연산을 해준다.

솔루션

def solution(N, number):
    answer = 0
    calculate=[set(),set(),set(),set(),set(),set(),set(),set(),set()]
    for i in range(1,9): # N은 8개까지 사용가능
        calculate[i].add(int(str(N)*i)) 
        for j in range(1,i): # 각 단계에서 짝을 맞추어 i개로 합치기
            for k in calculate[j]:
                for l in calculate[i-j]:
                    calculate[i].add(k+l)
                    calculate[i].add(k-l)
                    calculate[i].add(k*l)
                    if l != 0:
                        calculate[i].add(k/l)
        if number in calculate[i]:
            return i
    return -1

참조)

https://gurumee92.tistory.com/164