N으로 표현
🤡N으로 표현 (Lv.3)
🤑풀이
from itertools import permutations
import copy
def solution(N, number) :
b_memory = {N : 1}
a_memory = copy.deepcopy(b_memory)
for e in range(1, 9) :
a_memory[int(str(N)*e)] = min(a_memory.get(int(str(N)*e), e), e)
for n in b_memory :
if a_memory[n] < 8 :
a_memory[n+N] = min(a_memory.get(n+N, a_memory[n]+1), a_memory[n]+1)
a_memory[n-N] = min(a_memory.get(n-N, a_memory[n]+1), a_memory[n]+1)
a_memory[n*N] = min(a_memory.get(n*N, a_memory[n]+1), a_memory[n]+1)
a_memory[n//N] = min(a_memory.get(n//N, a_memory[n]+1), a_memory[n]+1)
corr_oper_lst = []
for v in a_memory.keys() :
if a_memory[v] < 8 :
corr_oper_lst.append(v)
nPr = list(permutations(corr_oper_lst, 2))
for a, b in nPr :
if a_memory[a]+a_memory[b] <= 8 :
a_memory[a+b] = min(a_memory.get(a+b, a_memory[a]+a_memory[b]), a_memory[a]+a_memory[b])
a_memory[a-b] = min(a_memory.get(a-b, a_memory[a]+a_memory[b]), a_memory[a]+a_memory[b])
a_memory[a*b] = min(a_memory.get(a*b, a_memory[a]+a_memory[b]), a_memory[a]+a_memory[b])
if b != 0 :
a_memory[a//b] = min(a_memory.get(a//b, a_memory[a]+a_memory[b]), a_memory[a]+a_memory[b])
b_memory = copy.deepcopy(a_memory)
return b_memory[number] if number in b_memory else -1
👩🏫 아이디어
- DP, 단순연산과 관계연산의 반복
- 무조건 8번 돌아야 하는 좋지 않은 풀이.
- 시간을 개선할 방법을 찾자.