[프로그래머스 Lv.3] N으로 표현 (동적계획법)

1. 문제 설명

2. 제한사항

3. 입출력 예

4. 문제 풀이

1) 동적계획법 설계

• 동적 계획법 : 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있음
• N = 5일 때,
  
• N = x일 때 (일반화)
  

2) 문제의 복잡도

• 실제로 만들어지는 결과의 개수
  
• 문제의 성질에 따라 동적 계획법으로 풀어냄으로써 탐색해야 하는 범위를 효과적으로 줄일 수 있음

3) 나의 풀이

• 중복을 제외하기 위해 집합을 사용함

def solution(N, number):
	# 주어진 N이 number와 같은 경우
    if N == number:
        return 1 # 바로 1 리턴

	# 반복되는 숫자를 집합에 하나씩 추가
    # {5}, {55}, {555}, ...
    d = []
    for i in range(1, 9):
        s = set()
        # 반복해서 만들어진 숫자가 number와 같으면
        if int(str(N)*i) == number:
            return i # 반복 횟수 리턴
        s.add(int(str(N)*i))
        d.append(s)

    for i in range(1, 8):
        for j in range(i):
            for num1 in d[j]:
                for num2 in d[i - j - 1]:
                    d[i].add(num1 + num2)
                    d[i].add(num1 - num2)
                    d[i].add(num1 * num2)
                    if num2 > 0: # ZeroDivisionError 방지
                        d[i].add(num1 // num2)
                if number in d[i]:
                    return i + 1 # N 사용 횟수 최솟값 리턴
    return -1 # 최솟값이 8보다 큰 경우 -1 리턴

4) 다른 풀이

def solution(N, number):
   if N == number:
       return 1
   s = [set() for x in range(8)]
   for i, x in enumerate(s, start = 1):
       x.add(int(str(N)*i))
   for i in range(1, len(s)):
       for j in range(i):
           for op1 in s[j]:
               for op2 in s[i - j - 1]:
                   s[i].add(op1 + op2)
                   s[i].add(op1 - op2)
                   s[i].add(op1 * op2)
                   if op2 != 0:
                       s[i].add(op1 // op2)
       if number in s[i]:
           answer = i + 1
           break
   else:
       answer = -1
   return answer