📙 N으로 표현

프로그래머스

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

왜 이렇게 풀었을까?

• dp 크기를 9로 제한하고, 반복문을 1부터 8까지만 돌린 이유는 문제에서 N이 1 이상 9 이하로만 사용되며, 최솟값이 8보다 크면 예외 처리를 해줄 것을 명시해뒀기 때문입니다.
• dp를 set으로 설정한 것은 중복 계산을 피하기 위해서입니다. 리스트로 설정했을 때보다 시간 효율성을 높일 수 있었습니다.
• 먼저 N이 한 자리 수이기 때문에 N으로 만들 수 있는 여러 자리의 수들은 미리 dp 배열에 집어넣었습니다.
• 이후 dp 배열을 순회하며 뽑아낸 수들로 사칙연산한 결과값들까지도 dp 배열에 추가해주었습니다.
• 그리하여 최종적으로 dp 배열의 요소 중 해당 값이 들어있다면 그 요소의 인덱스를 return하는 방식으로 구현해보았습니다 !