[프로그래머스 3단계]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

문제 풀이

• 이 문제는 상향식 방법(Bottom-up, Tabulation)의 다이나믹 프로그래밍 방법으로 풀이했습니다.
• 다이나믹 프로그래밍을 사용한 가장 큰 이유는 괄호의 존재때문입니다.
• 괄호가 없다면 단순히 앞에서부터 사칙연산을 모두 구해가며 number와 일치하는지만 확인하면 쉽게 풀이가 가능합니다.
• 괄호의 존재때문에 i개의 N으로 이루어진 숫자들의 모음은
  1. j개의 N으로 이루어진 사칙연산 결과 모음과
  2. i-j개의 N으로 이루어진 모음의 조합으로 이루어져 있다고 생각하고 문제에 접근해보겠습니다.(1=<j<4)

1. 우선 N이 number와 같다면 N 하나만 필요하므로 1을 리턴하고 dp는 list를 값으로 가지는 딕셔너리로 지정해둡니다.
   여기서 dp[i]는 i개의 N으로 이루어진 사칙연산의 결과값들의 list입니다.

    if N == number:
        return 1
    dp = collections.defaultdict(list)
    dp[1].append(N)

2. 33, 555같이 N이 사칙연산없이 이어붙어진 형태의 수들을 처리해줍니다.

    for i in range(2,9):
        dp[i].append(int(str(N)*i))

3. 이제 중복된 하위 문제들(Overlapping Subproblems)을 갖는 DP의 특징을 이용합니다. dp[j]의 요소들과dp[i-j]를 사칙연산한 결과를 순서대로 dp[i]에 넣어줍니다.
   • for문을 줄이기 위해 extend와 map, lambda로 각 사친연산의 결과를 한번에 처리합니다.
   • 0으로 나누는 경우 Error가 뜨는데 try,except 처리해줍니다.
   • 매 i번째 탐색마다 연산 결과에 타겟인 number가 존재한다면 i를 리턴합니다.
   • i=8까지 탐색했음에도 일치하는 결과값이 없다면 -1을 리턴합니다.

    for i in range(2,9):
        dp[i].append(int(str(N)*i))
        for j in range(1,5):
            # dp[i]는 dp[i-j]와 dp[j]의 조합
            for d_i in dp[i-j]:
                dp[i].extend(list(map(lambda x:x+d_i, dp[j])))
                dp[i].extend(list(map(lambda x:x-d_i, dp[j])))
                dp[i].extend(list(map(lambda x:x*d_i, dp[j])))
                try:
                    dp[i].extend(list(map(lambda x:x//d_i, dp[j])))
                except:
                    continue
        if number in dp[i]:
            return i
    return -1

최종 제출 코드

import collections
def solution(N, number):
    if N == number:
        return 1
    dp = collections.defaultdict(list)
    dp[1].append(N)

    for i in range(2,9):
        dp[i].append(int(str(N)*i))
        for j in range(1,5):
            # dp[i]는 dp[i-j]와 dp[j]의 조합
            for d_i in dp[i-j]:
                dp[i].extend(list(map(lambda x:x+d_i, dp[j])))
                dp[i].extend(list(map(lambda x:x-d_i, dp[j])))
                dp[i].extend(list(map(lambda x:x*d_i, dp[j])))
                try:
                    dp[i].extend(list(map(lambda x:x//d_i, dp[j])))
                except:
                    continue
        if number in dp[i]:
            return i

    return -1