[알고리즘][2][X] N으로 표현

 

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 합니다.
입출력 예
N	number	return
5	12	4
2	11	3
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

나의 풀이

- 이건 틀린 풀이다

- 틀린 이유는 5 + ( 5*5)의 경우를 생각하지 못했기 때문이다. 저렇게 하려면 BFS로는 불가능하다. 왜냐하면 BFS는 앞에서부터 늘려가는 식이기 때문이다. (5 + 5) * 5와 같이. 따라서 저런 경우를 생각해주려면 DP를 사용해야한다.

from collections import deque

def solution(N, number):
    # 최솟값을 구하는 문제이므로 그리디, DP, 탐색
    # 항상 최선의 선택을 할 수 없으므로 그리디 X
    # 탐색을 하되 이전의 결과를 사용할 수 있으므로 DP
    # 가능한 연산은 다음과 같다
    # 덧셈, 곱셈, 뺄셈, 나눗셈, 이어붙이기
    # 5^8 = 125 * 125 * 25 <= 200 * 200 * 100 = 4,000,000
    # 즉 완전 탐색을 해도 된다
    
    queue = deque()
    queue.append((N, 1))
    while queue:
        cur_number, n = queue.popleft()
        if n > 8:
            continue
        if cur_number == number:
            return n
        
        queue.append((cur_number + N, n+1))
        queue.append((cur_number - N, n+1))
        queue.append((cur_number * N, n+1))
        queue.append((cur_number // N, n+1))
        queue.append((int(str(cur_number) + str(N)), n+1))
    
    return -1

- 나의 풀이

- DP를 사용한 풀이다. for문이 4개여서 거부감이 들지만 시간초과는 나지 않는다.

- 원리는 이항정리와 비슷하다. dp[i]에는 dp[i-n] op dp[n] (n은 1부터 i-1까지)으로 구성된다고 보는 것이다.

- 저렇게 하면 dp[7]의 경우 최대 7^6만큼이 생기지만 이건 117649로 그렇게 큰 숫자가 아니다. 아마 그래서 이 문제에서는 8로 제한했을 것이다. 저 숫자가 커질수록 for문 한번의 부하(걸리는 시간)가 커진다.

- 시간복잡도를 구해보면 최대 시간은 8 * 8 * 4^6 * 4^6 <= 107374824로 시간초과가 나겠지만 이렇게 나오는 건 불가능하기 때문에 괜찮다.

- 또한 이렇게 불어나는 것을 줄이기 위해 set을 활용하여 중복을 제거하도록 하였다.

 

def solution(N, number):
    # 최솟값을 구하는 문제이므로 그리디, DP, 탐색
    # 항상 최선의 선택을 할 수 없으므로 그리디 X
    # 탐색을 하되 이전의 결과를 사용할 수 있으므로 DP
    # 가능한 연산은 다음과 같다
    # 덧셈, 곱셈, 뺄셈, 나눗셈, 이어붙이기
    # 5^8 = 125 * 125 * 25 <= 200 * 200 * 100 = 4,000,000
    # 즉 완전 탐색을 해도 된다
    
    if N == number:
        return 1
    dp = [[] for _ in range(9)]
    dp[1].append(N)
    
    for i in range(2, 9):        
        dp[i].append(int(str(N)*(i)))
        for j in range(1, i):
            for ele1 in dp[j]:
                for ele2 in dp[i-j]:
                    dp[i].append(ele1 + ele2)
                    dp[i].append(ele1 * ele2)
                    dp[i].append(ele1 - ele2)
                    dp[i].append(ele2 - ele2)
                    if ele2 != 0:
                        dp[i].append(ele1 // ele2)
                    if ele1 != 0:
                        dp[i].append(ele2 // ele1)
        for ele in dp[i]:
            if ele == number:
                return i
            
        dp[i] = list(set(dp[i]))
        
    return -1

아래 코드는 리팩토링을 한 것으로 불필요하게 dp[i]에 ele2 - ele1 같이 중복 코드가 있었다. 그럴 필요가 없다. 이중 for문 돌며 다 거치기 때문이다.

def solution(N, number):
    # 최솟값을 구하는 문제이므로 그리디, DP, 탐색
    # 항상 최선의 선택을 할 수 없으므로 그리디 X
    # 탐색을 하되 이전의 결과를 사용할 수 있으므로 DP
    # 가능한 연산은 다음과 같다
    # 덧셈, 곱셈, 뺄셈, 나눗셈, 이어붙이기
    # 5^8 = 125 * 125 * 25 <= 200 * 200 * 100 = 4,000,000
    # 즉 완전 탐색을 해도 된다
    
    if N == number:
        return 1
    dp = [[] for _ in range(9)]
    dp[1].append(N)
    
    for i in range(2, 9):        
        dp[i].append(int(str(N)*(i)))
        for j in range(1, i):
            for ele1 in dp[j]:
                for ele2 in dp[i-j]:
                    dp[i].append(ele1 + ele2)
                    dp[i].append(ele1 * ele2)
                    dp[i].append(ele1 - ele2)
                    if ele1 != 0:
                        dp[i].append(ele2 // ele1)
                        
        for ele in dp[i]:
            if ele == number:
                return i
            
        dp[i] = list(set(dp[i]))
        
    return -1