[프로그래머스] N으로 표현 (파이썬 풀이)

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

문제 설명

아래와 같이 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번만 사용하여 표현할 수 있습니다.

제출 코드

def solution(N, number):
    d = []
    for i in range(1,9):
        # 중복 제거를 위한 set 사용
        temp = set()
        # N을 단순히 이어붙였을 경우
        temp.add(int(str(N)*i))
        for j in range(i-1):
            for x in d[j]:
                for y in d[-j-1]:
                    temp.add(x+y)
                    temp.add(x*y)
                    temp.add(x-y)
                    if y != 0:
                        temp.add(x//y)
        if number in temp:
            return i
        d.append(temp)
    return -1

N과 사칙연산으로 다른 숫자를 표현하는 경우를 생각해보자. 덧셈, 뺄셈, 곱셈, 나눗셈, 숫자이어붙이기(예 : 5 & 5 => 55)가 있다. 

문제에서 N은 최대 8번까지 쓸 수 있다고 했으니 1~8개의 N을 사용해서 만들 수 있는 수의 집합 리스트를 만들고 그 집합에서 number가 처음 나오는 경우를 구하면 된다.

for j in range(i-1):
    for x in d[j]:
        for y in d[-j-1]:

첫번째 줄의 for문은 N의 개수를 하나씩 늘려서 계산하기 위한 for문이다.

 

두번째 줄과 세번째 줄의 for문은 만약 j개의 N로 수를 표현한다고 했을 때,

(1개의 N으로 표현한 수) & (j-1개의 N으로 표현한 수)의 사칙연산,

(2개의 N으로 표현한 수) & (j-2개의 N으로 표현한 수)의 사칙연산,

...

( j-1개의 N으로 표현한 수) & (1개의 N으로 표현한 수)의 사칙연산,

이런 식으로 모든 경우의 수를 구하기 위한 for문이다. 

뺄셈과 나눗셈은 순서가 중요하기 때문에 0부터 j까지 모두 계산한다.

 

참고 블로그 : https://alreadyusedadress.tistory.com/115