[프로그래머스] Lv3. N으로 표현 DP 🙁

N으로 표현

문제 설명

아래와 같이 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 합니다.

입출력 예Nnumberreturn

5	12	4
2	11	3

 

 

5를 1번 사용

5

5를 2번 사용

55, 5 * 5, 5 + 5, 5 / 5, 5 - 5  => 55, 25, 10 ,1, 0

5를 1번 사용 (사칙 연산) 5를 1번 사용

5를 3번 사용

555
55 * 5, 55 + 5, 55 / 5, 55 - 5  => 225, 60, 11, 50
(5 * 5) * 5, (5 * 5) + 5, (5 * 5) / 5, (5 * 5) - 5  => 125, 30, 5, 20
(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

5를 2번 사용 (사칙 연산) 5를 1번 사용
5를 1번 사용 (사칙 연산) 5를 2번 사용 => /와 -는 자리가 바뀌면 다른 값

5를 4번 사용

5를 1번 사용 (사칙 연산) 5를 3번 사용
5를 2번 사용 (사칙 연산) 5를 2번 사용
5를 3번 사용 (사칙 연산) 5를 1번 사용

 

이렇게 규칙을 가지고 있어서 각각의 숫자 사용 횟수로 만들 수 있는 숫자들의 전체를 저장하는 배열을 dp로 두고, 반복문을 1부터 9까지 돌면서 각각의 사용 횟수마다 만들 수 있는 숫자들의 조합을 찾는다. 반복 중에 number가 나오면 반복을 그만둔다.

 

조건에서 number는 1 ~ 32000이므로 빼기 연산의 결과로 음수가 나오면 안되고, 나누기 연산에서 나머지는 무시해야 하므로 나누기 연산의 결과가 소수인지 아닌지 확인해야 한다!

def solution(N, number):
    dp = [[] for i in range(9)]
    for i in range(1, 9):
        comb_set = set()
        comb_set.add(int(str(N) * i)) #55, 555, ... 이런건 기본으로 추가해두기
        for j in range(1, i):
            for operand1 in dp[i - j]:
                for operand2 in dp[j]:
                    plus = operand1 + operand2
                    minus = operand1 - operand2
                    multi = operand1 * operand2
                    
                    comb_set.add(plus)
                    comb_set.add(multi)
                    if minus >= 0:
                        comb_set.add(minus)
                    if operand2 != 0:
                        div = operand1 / operand2
                        if div % 1 == 0: #소수가 X
                            comb_set.add(int(div))
        if number in comb_set:
            return i
        for comb in comb_set:
            dp[i].append(comb)
    
    return -1