[프로그래머스] N으로 표현 (Python)

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

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

 

def solution(N, number):
    if N == number:
        return 1
    dp = [set() for _ in range(9)]
    for i in range(1, 9):
        dp[i].add(int(str(N)*i))
        for j in range(1, i):
            for y in dp[j]:
                for x in dp[i-j]:
                    dp[i].add(y+x)
                    dp[i].add(y-x)
                    dp[i].add(y*x)
                    if x != 0:
                        dp[i].add(y//x)
        if number in dp[i]:
            return i
        dp.append(dp[i])
    return -1

 

✏️ 메모

• 중복을 위해 set 사용
• set은 add, 인덱싱 불가능