[프로그래머스] N으로 표현/Python - Lv.3

❓문제

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

프로그래머스

성능 요약

메모리: 11 MB, 시간: 19.30 ms

 

 

문제 설명

아래와 같이 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

✍🏻풀이

N과 number가 같다면 무조건 최솟값을 1이 될 수 밖에 없으므로 같은 경우에는 1을 반환한다.

N을 두 번 사용하는 경우는 55, 5/5, 5x5, 5+5, 5-5가 있다. 이걸 잘 생각해보면 N과 연산자 조합을 이용하여 두 번 사용하는 경우를 구할 수 있다는 것을 알 수 있다.
그럼 N을 세 번 사용하는 경우는 N을 두 번 사용하는 경우, 연산자, 그리고 N을 한 번 사용하는 경우의 조합이라고 생각할 수 있다.
예를 들어, N을 두 번 사용하는 경우로 5+5, 연산자는 -, 5라고 하면 이 조합은 5 + 5 - 5가 된다. 그리고 이것은 순서가 정해져 있는 것이 아니므로 반대로 5 - 5 + 5 조합도 된다. 55 + 5와 5 + 55의 경우에는 값이 같다. 그러므로 set을 이용하여 중복된 값은 존재하지 않도록 한다.
그리고 제약사항에서 최솟값이 8보다 큰 경우는 -1을 반환하라고 했으므로 for문을 돌며 발견되지 않은 경우 -1을 반환하면 된다.

💻코드

def solution(N, number):
    if N == number:
        return 1
    
    dp = [set() for _ in range(9)]
    dp[1].add(N)
    x = N
    for i in range(2, 9):
        dp.append(set())
        x = 10 * x + N
        dp[i].add(x)
        for j in range(i):
            for op1 in dp[j]:
                for op2 in dp[i-j]:
                    dp[i].add(op1 + op2)
                    dp[i].add(op1 - op2)
                    dp[i].add(op1 * op2)
                    if op2 != 0:
                        dp[i].add(op1 // op2)
        
        if number in dp[i]:
            return i
        
    return -1

📍후기

DP는 맞는데 간단한 DP 문제만 보다보니 이런 DP문제를 보면 어떻게 풀어야할지 감이 잘 잡히지 않는다. 조합하면 된다고 생각하고 그 이상으로는 생각하지 못하는 내 자신이 너무 답답..