N으로 표현 (Python)

https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=python3 

프로그래머스

[문제 요약]

숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하는 solution

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

[해결 방법]

• 작은 문제부터 해결하여 그 값이 있으면 연산하지 않고 그걸 참고하는 bottom-up 방식
• N을 사용 횟수의 최댓값이 8이므로 8개의 집합 생성
  • 0부터 8까지 9개의 집합을 생성하긴 했지만, 필요 X
• N 사용 횟수가 2번이면 NN, N+N, N-N, N*N, N/N 연산한 값이 집합에 들어감
  
  • ex) N이 3개면 NNN, (N=1 값 + N=2 값), (N=1 값 - N=2 값), (N=1 값 * N=2 값), (N=1 값 / N=2 값), (N=2 값 + N=1 값), (N=2 값 - N=1 값), (N=2 값 * N=1 값), (N=2 값 / N=1 값)
• N이 i개일 때 연산값을 추가했다면, 해당 집합에서 number 발견 시 i return 후 종료
  • N 사용 횟수의 최솟값을 구하는 건데 bottom-up 방식을 사용해 1부터 시작했기 때문에 빨리 발견 될수록 사용 횟수가 적은 것이라 판단
• for문을 다 돌아도 number 발견하지 못하면 N의 최대 사용 횟수인 8번이 넘은 것이므로 -1 retrurn