Programmers - N으로 표현[파이썬(python)]

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - 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

 

---

문제 풀이

2차원 dp테이블을 활용하여 문제를 풀 수 있다.

dp[i]는 N을 i개 사용하여 표현할 수 있는 모든 수를 저장한다.

N=5일 때 5를 하나만 사용하여 표현할 수 있는 수는 5 하나 이므로 dp [1] = [5]가 된다.

dp [2]는 어떻게 구할 수 있을까?

먼저 사칙연산 없이 5를 2번 사용하는 55를 dp [2]에 추가한다. 이후 dp [1]과 dp [1] 간의 사칙연산을 수행한 결과가 될 것이다.

dp [2] = [55, 5+5, 5-5, 5/5, 5*5]가 된다.

 

dp [3] = [555] + [dp [2]와 dp [1] 간의 사칙연산 결과] + [dp [1]과 dp[2]간의 사칙연산 결과]가 된다.

여기서 dp[1]과 dp [2], dp [2]와 dp [1] 간의 사칙연산을 구해주는 이유는 '-'와 '/' 연산은 두 수의 순서가 바뀌면 값이 바뀌기 때문이다.

dp [1][0] = 5, dp [2][0] = 55 일 경우 5 - 55 = -50이 되지만 55 - 5는 50이 된다. -50은 제한사항에 맞지 않는 수이지만 다른 경우에 i개의 수를 사용하여 표현할 수 있는 수를 모두 구하지 못할 여지가 있기 때문에 두 경우를 모두 고려해야 한다.

 

j = 1 ~ (i-1) 일 때 점화식은 아래와 같다.

dp [i] = [str(N)*i] + [dp [i-1]과 dp [i-(i-1)] 간의 사칙연산] +... + [dp [i-j]과 dp [i-(i-j)] 간의 사칙연산]

구현 코드

코드 링크 : N으로 표현

def operation(n1, n2, operator):
    if operator == '+':
        return n1 + n2
    elif n2 != 0 and operator == '/':
        return int(n1 / n2)
    elif operator == '*':
        return n1 * n2
    else:
        return n1 - n2
    
def solution(N, number):
    if N == number:
        return 1
        
    operators = ['+', '/', '*', '-']
    dp = [[] for _ in range(9)]
    dp[0].append(0)
    dp[1].append(N)

    for i in range(2, 9):
        if int(str(N)*i) == number:
            return i
        dp[i].append(int(str(N)*i))
        for j in range(1, i):
            k = i-j
            for n1 in dp[j]:
                for n2 in dp[k]:
                    for op in operators:
                        result = operation(n1, n2, op)
                        if result == number:
                            return i
                        dp[i].append(result)
    return -1