[프로그래머스] N으로 표현 파이썬 풀이

[문제 링크]

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

[입출력 예]

N	number	return
5	12	4
2	11	3

[소스코드]

def solution(N, number):
    possible_set=[[]] #1. possible_set의 i번째 원소는
    # 0번 인덱스는 쓰지 않기 때문에 빈 리스트를 채운다.
    # 2. i개의 숫자로 만들 수 있는 숫자 종류이다.
    # 3. 가장 먼저 그 수 i개를 그대로 붙여서 만들 수 있는 것을 추가한다.

    for i in range(1,9):
        temp=[]
        temp.append(int(str(N)*i))

        for j in range(1,i//2+1):
            print(j,i//2+1)
            for a in possible_set[j]:
            #4. possible_set j번째와 i-j번째의 연산 결과를 모은다.
            # 두 연산 결과를 합치면 결국 i개의 N을 이용해 만든 결과가 나온다.
            # 예를 들어 i=5면 a가 2,b가 3일 때의 결과와
            # b가 3 a가 2일 때의 결과는 같을 것이므로 절반(올림)만 조회한다
            # i가 2일 때 a=1 b=1
            # i가 3일 때 a=1 b=2
            # i가 4일 때 a=1 b=3 , a=2 b=2
            # 두 개 다 고려하려 하지말고 하나만 탐색범위를 정확히 정하자

                for b in possible_set[i-j]:
                    temp.append(a+b)
                    temp.append(a-b)
                    temp.append(b-a)
                    temp.append(a*b)
                    if b!=0:
                        temp.append(a/b)
                    if a!=0:
                        temp.append(b/a)
        possible_set.append(temp)
        if number in possible_set[i]: return i
        #5.해당하는 타깃이 i개로 만들 수 있다는 의미이다.
    return -1