N으로 표현

프로그래머스

어려ㅂ다 후하후하

방법

1. 주어진 숫자 N으로 각 횟수 당 만들 수 있는 숫자 조합을 만든다.
2. 만들어진 숫자 조합에 number로 주어진 숫자가 있는지 확인한다.
3. 만약 있다면 그 지점에서의 횟수를 답으로 리턴
4. 없다면 횟수를 하나 늘리고 가능한 숫자 조합을 만들고 1~3 반복

N=1일 때 5 하나로 만들 수 있는 수 = 5

N=2) 55, 10(5+5), 25(5*5), 1(5/5), 0(5-5)
-> N=1일 때의 수와 N=1일 때의 수를 각각 사칙연산

N=3) 555, 15(5+5+5), 50((5+5)*5), 2((5+5)/5), 5((5+5)-5), 30(5*5+5), 20(5*5-5), 5(5*5/5), 125(5*5*5)....
-> N=1일 때의 수와 N=2일 때의 수를 각각 사칙연산

def solution(N, number):
    # nums[i]는 i개의 수로 만들 수 있는 조합
    nums = [0, [N]]
    
    if N == number:
        return 1
    
    for i in range(2, 9):
        num_set = []
        # 이어붙여서 만들기
        ni = int(str(N)*i)
        num_set.append(ni)
        
        # 연산해서 만들기
        # i가 5일 때, 1&4, 2&3으로 만들 수 있음. 3&2 4&1은 중복이기 때문에 i의 절반까지만 
        for j in range(1, i//2+1):
            for x in nums[j]:
                for y in nums[i-j]:
                    num_set.append(x+y)
                    num_set.append(x-y)
                    num_set.append(y-x)
                    num_set.append(x*y)
                    if y!=0:
                        num_set.append(x/y)
                    if x!=0:
                        num_set.append(y/x)
                        
            if number in num_set:
                return i
            nums.append(num_set)
    # 8개로 만들 수 없으면 -1리턴
    return -1