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

📕 문제

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

코딩테스트 연습 - N으로 표현

 

💡 풀이법

1. 1부터 9까지 n을 사용하는 갯수를 늘려가면서 해당 갯수에서 만들 수 있는 결과값을 all_case에 넣는다.

2. n을 2번 사용하면 1번 사용한 결과값을 1번 사용한 결과값과 연산한 값들이 만들어진다.

3. n을 3번 사용하면 1번 사용한 결과값과 2번 사용한 결과값을 연산한 값들이 만들어진다.

4. n을 4번 사용하면 1번 사용한 결과값과 2번 사용한 결과값을 연산한 값이 만들어 지고, 2번 사용한 결과값과 2번 사용한 결과값을 연산한 값들이 만들어진다.

5. 이렇게 5번 사용하면 (1,4), (2,3) 이렇게 연산한다. 이런식으로 for문을 돌면서 결과값을 구해주고 만약 타겟넘버가 나오면 그때 for문을 break를 해준다.

 

def solution(N, number):
    answer = -1
    dp = []

    for i in range(1,9) :
        all_case = set()
        check_number = int(str(N)*i)
        all_case.add(check_number)

        for j in range(0,i-1):
            for op1 in dp[j]:
                for op2 in dp[-j-1] :
                    all_case.add(op1 - op2)
                    all_case.add(op1 + op2)
                    all_case.add(op1 * op2)
                    if op2 != 0:
                        all_case.add(op1 // op2)

        if number in all_case:
            answer = i
            break

        dp.append(all_case)
        print(dp)       
    return answer

N = 5
number = 12
print(solution(N, number))