[Programmers]Python_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 합니다.

 

코드

def solution(N, number):
   #N과 표현할 숫자 number와 같으면 자기 자신으로 표현하는 방법밖에 없음
   if N == number:
       return 1
       
   stack = [0, {N}] #N의 Index개수 별로 표현할 수 있는 숫자들 저장
   
   for i in range(2, 9): #제한사항에서 8보다 크면 -1을 return하므로 8개까지 반복
       numbers = {int(str(N) * i)} #i개의 N이 연속으로 있는 경우를 일단 저장
       
       for j in range(1, i // 2 + 1):
           for k in stack[j]:
               for v in stack[i - j]:
                   #사칙연산으로 표현할 수 있는 값들 모두 저장
                   numbers.add(k + v)
                   numbers.add(abs(k - v)) #음수가 나올 수 있으므로 abs로 절댓값 변환
                   numbers.add(k * v)
                   if k != 0:
                       numbers.add(v // k)
                   if v != 0:
                       numbers.add(k // v)
                       
       if number in numbers: #해당 개수에 number가 있으면 i return
           return i
       stack.append(numbers)
           
   return -1 #8개까지 표현했는데 없으면 -1 return

 

진행 순서

예제 #1

 N = 5, number = 12

 

1) stack = [0, {5}]

 

- N이 2개일 때

  N = 1개, N = 1개

2) numbers = {55}

3) numbers.add(10), numbers.add(0), numbers.add(25), numbers.add(1), numbers.add(1)

4) numbers = {55, 10, 0, 25, 1, 1}

5) number in numbers => False

6) stack = [0, {5}, {55, 10, 0, 25, 1, 1}]

 

- N이 3개일 때

  N = 1개, N = 2개

  N = 2개, N = 1개  -> N = 1개, N = 2개일 경우와 같으므로 무시한다 (코드 상 range(1, i // 2 + 1) 으로 해결)

7) numbers = {555}

8) numbers = {0, 2, 4, 5, 6, 555, 11, 15, 50, 275, 20, 60, 125, 30}

9) number in numbers => False

10) stack = [0, {5}, {55, 10, 0, 25, 1, 1}, {0, 2, 4, 5, 6, 555, 11, 15, 50, 275, 20, 60, 125, 30}]

 

- N이 4개일 때

  N = 1개, N = 3개

  N = 2개, N = 2개

  N = 3개, N = 1개

11) numbers = {5555}

12) numbers = {0, 1, 2, 3, 4, 5, 6, 7, 130, 9, 10, 11, 12, 270, 15, 16, 20, 150, 280, 25, 26, 24, 30, 35, 550, 300, 45, 560, 50, 5555, 54, 55, 56, 65, 75, 80, 3025, 2775, 1375, 100, 110, 111, 625, 120, 250}

13) number in numbers => True

14) return 4