[프로그래머스] 42895. N으로 표현

Programmers - 42895. N으로 표현

접근

일단, N을 1번 사용했을 때 ~ 8번 사용했을 때를 모두 순회하며 확인하면 될 것 같음.

일단 N = 3으로 예시를 들어서 한번 생각해 보자.

• N을 1번 사용했을 때

{3}

• N을 2번 사용했을 때

{33}, {3+3, 3-3, 3/3, 3*3} => {33, 6, 0, 1, 9}

• N을 3번 사용했을 때

여기부터 이제 사칙연산에 어떤 수를 사용하느냐에 따라 갈리는데

• • 3, 3, 3을 사용

    • 3+3과 3을 사용
    • 3-3과 3을 사용
    • 3/3과 3을 사용
    • 3*3과 3을 사용

  • 33, 3을 사용

    • 33*3, 33-3, 33+3, 33/3, 3*33, 3-33, 3+33, 3/33

결국 N을 3번 사용할 때의 결과값은

1. N을 1번 사용했을 때 (+, -, *, /) N을 2번 사용했을 때

2. N을 2번 사용했을 때 (+, -, *, /) N을 1번 사용했을 때

이 두 가지 경우의 수로 나눌 수 있게 된다.

다음으로,

• N을 4번 사용했을 때

의 경우는 이제

1. N을 1번 사용 (연산) N을 3번 사용
2. N을 2번 사용 (연산) N을 2번 사용
3. N을 3번 사용 (연산) N을 1번 사용

이 세 가지 경우의 수를 모두 게산해주면 된다.

이런 식으로 8번 계산할 때까지 순회해보면 될 듯.

 

자료구조는 set을 사용하면 된다.

겹치는 숫자는 필요없기 때문.

 

def solution(N, number):
    set_num = [set()]
    # i = 1 ~ 8
    for i in range(1, 9):
        set_i = set()

        if i == 1:
            set_i.add(N)
        elif i == 2:
            new = [N*11, N-N, N*N, N+N, int(N/N)]
            set_i.update(new)
        else:   # i = 3 ~ 8
            for j in range(1, i):
                for num1 in set_num[i-j]:
                    for num2 in set_num[i-(i-j)]:
                        new = [num1+num2, num1-num2, num1*num2]
                        if num2 != 0:
                            new.append(int(num1/num2))
                        set_i.update(new)

            no_symbol_num = int(str(N)*i)
            set_i.add(no_symbol_num)

        if number in set_i:
            return i

        set_num.append(set_i)
        
    return -1

 

set_num 에는 아래처럼 담기게 됨. (N = 5)

[{}, {5}, {0, 1, 10, 55, 25}, {3개 이용}, {4개 이용}, {5개 이용}...]