[프로그래머스/Level3] N으로 표현 (Python)

❓ 문제

문제 설명
아래와 같이 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 합니다.
  
  입출력 예입출력 예 설명
  예제 #1
  문제에 나온 예와 같습니다.
  
  예제 #2
  11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

🔎 문제 분석

• 동적 계획법(Dynamic Programming)이란 무엇인가?
  • 보통 최적화 문제를 다루는 데 동적 계획법이 많이 사용됨.
  • 재귀적인 방식으로 보다 작은 부분 문제로 나누어 부분 문제를 먼저 푼 후에 이를 조합해 전체 문제 해답에 이르는 방식.
  • 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정 -> 탐색 범위를 한정할 수 있음.
  • 복잡도는 선형 함수의 형태를 가진다.
  • 대표적인 예로는 Knapsack Problem이 있다.
• 어떻게 이 문제를 동적 계획법(Dynamic Programming)으로 풀 수 있을까?
  • N을 한 번 사용해서 만들 수 있는 수를 알면 두 번 사용해서 만들 수 있는 수도 알 수 있고 N 번 사용해서 만들 수 있는 수 역시 알 수 있다.
  • 이후 그렇게 만들어진 수끼리 사칙연산을 통해 계산하여 구하고자 하는 값이 나올 때까지 이 과정을 반복한다.

❗ 풀이

• 연산을 반복할 시 중복이 발생할 수 있는가를 따졌을 때 이 문제는 중복이 발생할 수 있다. 중복이 발생할 경우 복잡도가 올라가기 때문에 중복을 막아 주는 자료 구조 set을 사용하기로 한다.
• 최솟값이 8보다 크면 -1을 return한다는 조건이 있으므로 9번부터는 반복하여 계산할 필요가 없다.
• 케이스 9에서 계속 실패가 떴다. 원인은 N과 number가 같을 경우 따로 계산해 줄 것 없이 바로 값을 만들 수 있으므로 1이 return 되어야 한다는 것을 빼먹은 것이다. N: 5, number:5 return:1을 테스트 케이스로 추가하여 if N == number일 때 return 1을 해 주도록 추가해 주었다.

def solution(N, number):
    answer = 0
    s = [set() for x in range(8)]  #8개의 set이 만들어지도록 초기화, s에는 8 번 사용해서 담길 수 있는 수들의 집합이 담긴다
    
    if N == number:  #N과 number가 같은 경우 더 계산할 것 없이 1이 return되므로 for문을 쓰기 전에 처리해 준다.
    	return 1
    
    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) #op2가 0인 경우 division error 발생
        if number in s[i]:  #그때그때 확인을 하면 연산이 단순할 수도 있겠지만 이렇게 list를 확인하는 것이 코드가 깔끔함
            answer = i + 1
            break
    else:
        answer = -1
            
    return answer