[progarmmers] N으로 표현

KwonSC·2022년 6월 8일
0

programmers - Python

목록 보기
23/23
post-thumbnail

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


Code

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

Solution

dp 리스트는 만들 수 있는 숫자들이고 i는 사용하는 숫자의 개수, numi개의 숫자를 사용할때 만들 수 있는 숫자들이다. for 문을 돌면서 numi만큼 반복되는 숫자를 넣고 dp를 돌면서 (j, -j - 1인 이유는 dp[j]와 dp[-j - 1]를 연산한 결과는 i만큼의 숫자를 사용하기 때문) 각각 사칙연산을 수행하며 num에 결과를 넣고 만약 numnumber가 있으면 i를 리턴, 아니면 dpnum을 삽입하고 반복문을 순회한다. 만약 끝까지 리턴할 값이 없으면 -1을 리턴한다.

0개의 댓글