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

https://programmers.co.kr/learn/courses/30/lessons/42895?language=python3 

코딩테스트 연습 - N으로 표현

 

모든 number는 N으로 표현 가능하기 때문에 정답의 최댓값이 8로 제한이 되어있다.

-> 이를 이용해서 N을 1부터8번 사용해서 사용해서 얻을 수 있는 모든 경우의수를 계산해주었다.

계산 방법을 4번 사용했을때로 예시를 들면

4= 1(사칙연산)3, 3(사칙연산)1, 2(사칙연산)2

이렇게 전에 계산한 연산 결과들을 이용해서 구해나갈 수 있다.

위에서 1,3 3,1 을 따로 둔 이유는 - 나 // 같은 경우는 교환법칙이 성립하지 않아서 이다.

그렇게 짠 코드는 아래와 같다

def solution(N, number):
    N=str(N)
    number=str(number)
    
    dp=[{N*(i+1)} for i in range(8)]
    cal=['*','+','-','//']

    for i in range(8):
        
        for j in range(i):
            for first in dp[j]:
                for second in dp[i-j-1]:
                    for c in cal:
                        try:
                            result=eval(first+c+second)
                        except:
                            continue
                        if result > 32000:
                            continue
                        dp[i].add(str(result))
        if number in dp[i]:
            return i+1
                        
    return -1

개선 사항으로는 +와* 는 교환법칙이 성립하기 때문에 이때문에 생기는 중복 연산을 제거해주면 조금 연산이 빨라지지 않을까? 싶었다. (귀찮아서 안했다.)