[프로그래머스] 👨‍🎓 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 합니다.

😃 나의 풀이

dic = {0:1}

def DP(result, level, array, target):
    if level<9:
        if result in dic :
            if dic[result] > level:
                dic[result] = level
                if result == target:
                    return level
                for i in range(0,8):
                    DP(result-array[i], level +i+1, array,target)
                    DP(result//array[i], level +i+1, array,target)
                    DP(result*array[i], level +i+1, array,target)
                    DP(result+array[i], level +i+1, array,target)
        else:
            dic[result] = level
            if result == target:
                return level
            for i in range(0,8):
                DP(result-array[i], level +i+1, array,target)
                DP(result//array[i], level +i+1, array,target)
                DP(result*array[i], level +i+1, array,target)
                DP(result+array[i], level +i+1, array,target)

def solution(N, number):
    answer = 0
    array = []
    your_dict = {0:1}
    num = N
    for i in range(0,8):
        array.append(num)
        num = num*10 + N
    DP(0, 0, array, number)
    if(number in dic):
        answer = dic[number]
    else: answer = -1
    return answer

동적계획법^{Dynamic Programming} 알고리즘에 속한 문제였지만, 파이썬으로 DP를 처음 풀어서 DP로는 도저히 풀 방법이 안나서 그냥 무차별 대입^{Brute force}를 통해 모든 결과값을 사전식으로 저장해서, 작은 시행의 결과 값만 남게 짜보았다.

👀 눈여겨 볼 만한 풀이

def solution(N, number):  
  S = \[{N}\]  
  for i in range(2, 9):  
    case\_set = {int(str(N)\*i)}
    # 사용된 숫자는 중복을 없에기 위해 전체 길이의 반까지만 확인
    for x_idx in range(int(i/2)):
        # x는 N이 x_idx+1번 쓰인 경우
        for x in S[x_idx]:
            # y는 N이 i-x_idx-1번 쓰인 경우
            for y in S[i - x_idx - 2]:
                # x와 y를 이용했기 때문에 전체 N이 i번 쓰인 경우입니다
                case_set.add(x+y)
                case_set.add(x-y)
                case_set.add(y-x)
                case_set.add(x*y)
                if x!=0: case_set.add(y//x)
                if y!=0: case_set.add(x//y)
  if number in case_set:
      return i
  S.append(case_set)
return -1

N사용이 2인 사칙연산부터 N사용이 8인 사칙연산까지 반복하면서 목표값인 number가 case\_set에 있는 지 확인하는 방법이다. S의 원소인 집합의 인덱스는 5가 사용된 숫자보다 1 작은 값으로 정하고 풀이를 진행합니다. x는 N이 x\_idx+1번 쓰인 경우에 해당하고, y는 N이 i-x\_idx-1번 쓰인 경우입니다. x와 y의 원소를 이용해서 case\_set에 사칙연산으로 나올 수 있는 결과값을 저장합니다. 해당하는 숫자가 존재할 시 바로 결과 값이 나오는 좋은 풀이법이고 N이 사용된 갯수에 따라 시행을 반복하고 이전 시행을 저장하여 이용하기 때문에 DP에 적합한 문제입니다.

여담이지만, 레벨 1 수준의 문제는 아닌 것 같습니다.