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

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

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

문제유형 : DP

 

문제풀이 :

• 숫자X를 n번 사용해서 만들수있는 숫자
  • 숫자 X를 n번 이어붙여서 만든 숫자
  • 숫자 X를 i번 사용해서 만들수있는 숫자와 숫자 X를 n-i번 사용해서 만들수 있는 숫자의 사칙연산의 결과 (1<=i<=n-1)
• 위 두가지경우를 최대8까지 수행한후 결과에 목표하는 숫자인 number가 있는지 없는지 확인한후에 리턴한다.

 

 

정답코드:

def solution(N, number):
    answer = 0
    dp = [set() for _ in range(9)]
    # 뒤에 그대로N을 붙이는 경우
    for i in range(1,9):
        dp[i].add(int(str(N)*i))
    
    if N == number:
        return 1
        
    i = 2
    # N을 i번써서 만들 수 있는 수
    while True:
        # x번과 i-x번 써서 만들수있는 경우의 사칙연산
        for j in range(1, i): #j가 1부터 i-1번까지 
            #dp[j]에 있는 숫자들과 dp[i-j]에 있는 숫자들로 사칙연산수행
            for num1 in dp[j]:
                for num2 in dp[i-j]:
                    dp[i].add(num1*num2)
                    if num2:
                        dp[i].add(num1//num2) 
                    dp[i].add(num1-num2)
                    dp[i].add(num1+num2)
        #print(dp[i])    
        
        if number in dp[i]:
            return i
        if i==8:
            return -1
        i += 1