[알고리즘] N으로 표현 문제 풀이 (Python)

문제보기

풀이

딕셔너리에 키값으로 N을 사용한 갯수 값으로 해당 갯수로 나타낼 수 있는 수를 Set에 저장한다. 예를 들면, {1: {5}, 2: {55, 10, 0, 25, 1}, 3: {...}, ... }

최솟값이 8보다 크면 -1을 return 합니다.

라는 조건이 있기때문에 딕셔너리의 키값은 8까지 될 것이다.
Set을 사용하는 이유는 중복되는 값을 제거하기 위해서 이다.

이때 딕셔너리의 값들을 채우기 위해서 이전의 값들을 사용할 수 있다. 예를 들어, N을 3번 사용해서 나올 수 있는 값들을 계산할 때 N을 1번 사용했을 때 값들과 N을 2번 사용했을 때의 값들을 연산해서 계산할 수 있다.
즉, dict[3]의 값들은 dict[1] 사칙연산 dict[2]의 값들과 dict[2] 사칙연산 dict[1]이 된다.

N을 1번 사용 (N1): N
N을 2번 사용 (N2): N1 op(사칙연산) N1
N을 3번 사용 (N3): N1 op N2, N2 op N1
N을 4번 사용 (N4): N1 op N3, N2 op N2, N3 op N1
...

코드

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