프로그래머스(동적계획법)-N으로 표현-Python

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

 

---

내 문제풀이

5를 1번 사용하는 경우 5

5를 2번 사용하는 경우 55 (5+5) (5-5) (5*5) (5//5)    -> 1번 사용하는 경우의 값을 활용하여 사칙연산 계산

5를 3번 사용하는 경우 555 (5+5)+5 (5+5)-5 (5+5)*5 (5+5)//5 (5-5)+5 (5-5)-5 (5-5)*5 ...     -> 1번 사용하는 경우의 값과 2번 사용하는 경우의 값 혼합 활용하여 사칙연산 계산

1. 위 처럼 패턴을 갖고 5를 4번 사용하는 경우 -> 1번 사용&3번 사용, 2번 사용& 2번 사용, 3번 사용&1번 사용 값을 활용한다.

2. n번 사용할 경우 n//2번을 넘어가면 이전 계산과 중복되므로 1~n//2+1 번까지 반복문을 수행한다. 반복문 내에서는 위의 패턴대로 각 숫자의 사용 횟수별 사칙연산을 수행한다.

3. 계산한 사칙연산 리스트에 number가 있다면 몇 번 사용했는지의 값(i)를 반환한다.

4. 계산한 사칙연산 리스트에 number가 없다면 다음 횟수 계산을 위해 total에 계산한 값 리스트(num_list)을 추가해준다.

5. 최솟값이 8보다 클 수 없다고 제한 조건을 주었기 때문에 반복문 내에서 정답이 반환되지 않으면 -1을 반환한다.

내 코드 - 파이썬

def solution(N, number):
    total = [0, [N]] # 사용횟수 별 계산 값 저장 리스트
    if N==number: return 1

    for i in range(2, 9):
        num_list = [int(str(N)*i)] # 단순 반복 값 초기화
        for j in range(1, i//2+1):
            for a in total[j]:
                for b in total[i-j]:
                    num_list.append(a+b)
                    num_list.append(a*b)
                    num_list.append(a-b)
                    num_list.append(b-a)
                    if a!=0 : num_list.append(b//a)
                    if b!=0 : num_list.append(a//b)
        if number in num_list : return i
        total.append(num_list)
    
    return -1