프로그래머스 DP / N으로 표현 (Python)

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

프로그래머스

 

1. 문제 설명

- 변수

• N : 1 ~ 9 이하 
• number : 1 ~ 32,000 이하

 

- 결과

N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 

 

- 주의사항

• 최솟값이 8보다 크면 -1

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

• 이처럼 5를 사용한 횟수 중에서 가장 작은 경우는 4를 찾기
• 나머지 제외

 

2. 문제 풀이

def solution(N, number):
    answer = -1
    dp = []
    # 1부터 8까지 반복
    for i in range(1, 9):
        numbers = set()  # i번 N을 사용하여 저장하는 집합 
        ns = int(str(N) * i) # N을 i번 이어붙인 숫자를 추가
        numbers.add(ns)
        
        for j in range(i - 1): # 모든 조합 생성
            for n1 in dp[j]:
                for n2 in dp[i - j - 2]:
                    # 덧셈, 뺄셈, 곱셈
                    numbers.update([n1 + n2, n1 - n2, n1 * n2])  
                    # 0으로 나누는 거 방지
                    if n2 != 0:
                        numbers.add(n1 // n2)
        # number가 집합 안에 있으면 저장
        if number in numbers:
            answer = i
            break
        # 만들 수 있는 숫자를 dp[i]에 저장 
        dp.append(numbers)
    return answer