[Algorithm] N으로 표현

리쫑·2023년 2월 7일
0

Algorithm

목록 보기
11/16

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번 돌아야 하는 좋지 않은 풀이.
  • 시간을 개선할 방법을 찾자.
profile
AI, Data Scientist 취업 준비생 입니다. 공부한 내용을 포스팅하고자 합니다. 방문해주셔서 감사합니다

0개의 댓글