[알고리즘] 프로그래머스 N으로 표현 / python

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

코딩테스트 연습 - N으로 표현 | 프로그래머스

 

DP로 풀어내는 문제.

만약, N=5일때

arr[0] 👉 5

arr[1] 👉 55 , 5+5, 5-5, 5*5, 5//5

이런식으로 전개된다

5를 4번 사용한 경우(arr[3])를 생각해보면,

arr[0] (+ - * //) arr[2]

arr[1] (+ - * //) arr[1]

arr[2] (+ - * //) arr[0]

에서 중복을 제거한 수들이 될것이다.

 

def solution(N, number):
    arr = [set() for i in range(8)]
    
    for i, num in enumerate(arr, start=1):
        num.add(int(str(N) * i))
    
    for i in range(1,len(arr)):
        for j in range(i):
            for op1 in arr[j]:
                for op2 in arr[i - j - 1]:
                    arr[i].add(op1 + op2)
                    arr[i].add(op1 - op2)
                    arr[i].add(op1 * op2)
                    if op2 != 0:
                        arr[i].add(op1 // op2)
        if number in arr[i]:
            answer = i+1
            break
    else:
        answer = -1
        
    return answer