[프로그래머스] N으로 표현(python 파이썬)

 

N = 1 일때 나타낼 수 있는 값

5

 

N = 2 일때 나타낼 수 있는 값

55, 5+5, 5-5, 5*5, 5/5

즉 N = 1의 집합을 조합해서 만든 경우이다.

 

N = 3 일때

555,

5+(5+5), 5-(5+5), (5+5)-5, (5+5)*5, (5+5)/5, 5/(5+5),

5+(5-5), 5-(5-5), (5-5)-5, (5-5)*5, (5-5)/5, 5/(5-5),

.... 이런식이다

즉

N = 1, N = 2의 조합이다.

N = 2, N =1( N = 1, N = 2와 중복임으로 생략)

 

N = 4 일때

N = 1, N = 3

N = 2, N = 2

N = 3, N = 1 ( N = 1, N = 3과 중복임으로 생략)

 

즉, 절반까지 구하면된다.

 

def solution(N, number):
    S = [0, {N}]
    if N == number:
        return 1

    for i in range(2, 9):
        case = {int(str(N) * i)}
        for j in range(1, i // 2 + 1):
            for x in S[j]:
                for y in S[i - j]:
                    case.add(x + y)
                    case.add(x - y)
                    case.add(y - x)
                    case.add(x * y)
                    if x != 0:
                        case.add(y // x)
                    if y != 0:
                        case.add(x // y)
        if number in case:
            return i
        S.append(case)
    return -1