https://programmers.co.kr/learn/courses/30/lessons/42895
def solution(N, number):
dp = []
for i in range(1, 9):
num = set()
num.add(int(str(N) * i))
for j in range(i - 1):
for x in dp[j]:
for y in dp[-j - 1]:
num.add(x + y)
num.add(x - y)
num.add(x * y)
if (y):
num.add(x // y)
if (number in num):
return i
dp.append(num)
return -1
dp
리스트는 만들 수 있는 숫자들이고 i
는 사용하는 숫자의 개수, num
은 i
개의 숫자를 사용할때 만들 수 있는 숫자들이다. for 문을 돌면서 num
에 i
만큼 반복되는 숫자를 넣고 dp
를 돌면서 (j, -j - 1인 이유는 dp[j]와 dp[-j - 1]를 연산한 결과는 i만큼의 숫자를 사용하기 때문)
각각 사칙연산을 수행하며 num
에 결과를 넣고 만약 num
에 number
가 있으면 i
를 리턴, 아니면 dp
에 num
을 삽입하고 반복문을 순회한다. 만약 끝까지 리턴할 값이 없으면 -1
을 리턴한다.