문제

문제 설명

아래와 같이 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
5	12	4
2	11	3

입출력 예 설명

예제 #1

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

예제 #2

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

풀이

1. s = [set() for x in range(8)]
   : s는 N을 1번부터 8번까지 사용하여 만들 수 있는 리스트이다. set을 사용하여 중복 결과를 제거한다!

2. s 리스트 순회하면서 i 번째 인덱스에 x값 삽입

for i, x in enumerate(s, start = 1):
    x.add(int(str(N) * i))

• : N = 5라면, x는 5, 55, 555, 5555 이런식으로 삽입

s[0] = {5}
s[1] = {55}
s[2] = {555}
s[3] = {5555} 
...

---

5를 5번 사용해서 만들 수 있는 숫자

5 1번 사용 (+ - * /) 5 4번 사용
5 2번 사용 (+ - * /) 5 3번 사용
5 3번 사용 (+ - * /) 5 2번 사용
5 4번 사용 (+ - * /) 5 1번 사용

숫자x를 n번 사용해서 만들 수 있는 숫자

x 1번 사용 (+ - * /) x (n-1)번 사용
x 2번 사용 (+ - * /) x (n-2)번 사용
x 3번 사용 (+ - * /) x (n-3)번 사용
...
x n-1번 사용 (+ - * /) x 1번 사용

3. for i in range(len(s)):
   : i = 0 ~ 7 (s[0] ~ s[7])

4. for j in range(i):
   : N을 i+1번 사용해서 만들 수 있는 숫자들을 구하기 위해 j를 순회.
   j는 0 ~ i-1 → 즉, s[j]와 s[i-j-1]을 조합해서 s[i]를 만든다.

for i in range(len(s)): # i: 0 ~ 7
        for j in range(i): # j: 0, 01, 012, 0123, ...
            for op1 in s[j]: # op1 : 피연산자1, N을 j+1번 사용하여 만들 수 있는 숫자들
                for op2 in s[i-j-1]: # op2 : 피연산자2, N을 i-j번 사용하여 만들 수 있는 숫자들
                    # op1과 op2를 사칙연산 --> 즉 N을 i+1번 사용하여 만들 수 있는 숫자를 구하게 되고 이를 s[i]에 대입
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)

예시) N이 5일 때 s[2]을 구하는 과정 (i=2)
= N을 3번 사용해서 만들 수 있는 숫자들을 구하는 과정이다. (555)

1️⃣ j=0 (첫 번째 경우)

s[0] (N을 1번 사용) {5}
s[1] (N을 2번 사용) {55, 10, 0, 25, 1}

s[0]과 s[1]의 모든 조합:
5 + 55 = 60
5 - 55 = -50
5 * 55 = 275
5 / 55 = 0 (정수 나눗셈이므로)
5 + 10 = 15, 5 - 10 = -5, 5 * 10 = 50, 10 // 5 = 2, ...


2️⃣ j=1 (두 번째 경우)

s[1] (N을 2번 사용) {55, 10, 0, 25, 1}
s[0] (N을 1번 사용) {5}

s[1]과 s[0]의 모든 조합:
55 + 5 = 60
55 - 5 = 50
55 * 5 = 275
55 / 5 = 11, 10 + 5 = 15, 10 - 5 = 5, ...

이 과정을 통해 s[2]는 {555, 60, 275, 15, 5, 50, 11, -5, -50} 등이 추가된다.

최종 코드

def solution(N, number):

    # s[i] : s는 N을 1번부터 8번까지 사용하여 만들 수 있는 리스트. set을 사용하여 중복 결과를 제거.
    s = [set() for x in range(8)] # s[0] ~ s[7]. N을 1개부터 8개 까지 사용하여 만든 값들이 number가 아니라면 -1
    for i, x in enumerate(s, start = 1): # s 리스트 순회하면서 i 번째 인덱스에 x값 삽입
        x.add(int(str(N) * i)) # 8개의 set 초기화. N이 5라면, s[0] = {5}, s[1] = {55}, s[2] = {555}, s[3] = {5555}, ...
        
    # s[i]를 돌면서 N을 i+1개 사용했을 때 만들 수 있는 숫자 구하기.
    for i in range(len(s)): # i: 0 ~ 7
        for j in range(i): # j: 0, 01, 012, 0123, ...
            for op1 in s[j]: # op1 : 피연산자1, N을 j+1번 사용하여 만들 수 있는 숫자들
                for op2 in s[i-j-1]: # op2 : 피연산자2, N을 i-j번 사용하여 만들 수 있는 숫자들
                    # op1과 op2를 사칙연산 --> 즉 N을 i+1번 사용하여 만들 수 있는 숫자를 구하게 되고 이를 s[i]에 대입
                    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]: # N을 i+1번 사용했을 때 찾는 값인 number가 존재 : i+1 return
            answer = i + 1
            break
        else: # N을 8번 사용했는데도 찾는 값 number가 존재 X : -1 return
            answer = -1
    return answer

---

참고

https://velog.io/@s2ul2/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4level3-N%EC%9C%BC%EB%A1%9C-%ED%91%9C%ED%98%84-Python%ED%8C%8C%EC%9D%B4%EC%8D%AC