프로그래머스 Level3 "N으로 표현"

문제

프로그래머스 'N으로 표현'

풀이

i = 1 : set( 5 )
i = 2 : set( 55, N[1] + N[1] )
i = 3 : set( 555, N[1] + N[2], N[2] + N[1] )
i = 4 : set( 5555, N[1] + N[3], N[2] + N[2], N[3] + N[1] )
.
.

예제와 같이N = 5일 경우 N[2]는 N[1]과 N[1]을 이어붙이거나 사칙연산한 것이고,
N[3]는 N[1]과 N[2]를 이어붙이거나 사칙연산한 것이다.
즉, N[i]는 N[1] ~ N[i-1]의 세트리스트를 가지고 만들수 있다.

또한, 한가지 주의 해야할 점이 사칙연산의 경우 순서가 바뀌면 그 결과가 바뀌므로 서로 순서를 바꾸어 사칙연산한 세트리스트를 만들어 합집합으로 묶어주어야 한다.

Python 코드

def solution(N, number):
  dp = [[]]
  for i in range(1, 9):
    temp = []
    for j in range(1, i):
      for k in dp[j]:
        for l in dp[i - j]:
          temp.append(k + l)
          if k - l >= 0:
            temp.append(k - l)
          temp.append(k * l)
          if l != 0 and k != 0:
            temp.append(k // l)
    temp.append(int(str(N) * i))
    if number in temp:
      return i
    dp.append(list(set(temp)))

  return -1