문제 링크

풀이 과정

• 사칙연산의 수행 순서 및 연산자에 따라, 연산의 결과가 다릅니다. 또한, 이를 아우르는 경우의 수는 무수하게 많을 것입니다.
• 언뜻 문제를 봤을 때, 쉽사리 문제의 풀이 방법이 떠오르지 않을 수 있습니다.
• 이런 순간에는, 제한 사항에 문제를 풀 수 있는 실마리가 있는 지 확인하는 과정이 필요합니다.
  • 숫자 N을 이용하여, 목표 숫자 number를 만들 때, 사용한 N의 갯수가 8보다 크면 -1을 반환합니다.
  • 저는 이 제한 조건을 역이용하여, 문제를 접근하도록 하겠습니다.
• N의 갯수를 1부터 8까지 순차적으로 증가시키면서, 모든 사칙연산 결과를 저장합니다.
  • 목표 숫자인 number가 사칙연산 결과물에 포함될 때, 해당 N의 갯수를 반환합니다.
  • 만약 N의 갯수가 8일 때도, number가 사칙연산 결과물에 포함되지 않는다면, -1을 반환합니다.
• 이때, N의 갯수에 따른 사칙연산 결과는 반복적으로 사용되므로, DP 방식으로 문제를 접근합니다.
  • dp[i]: i개의 숫자 N으로, 표현(사칙 연산)할 수 있는 모든 숫자 집합 (1≤ i ≤ 8)
  • 예컨대, dp[2]는 dp[3]~dp[8]을 계산할 때 모두 적용됩니다.

전체 코드

from collections import defaultdict

def solution(N, number):
	# dp[i]: N을 i번 사용해서 만들 수 있는 수들의 집합
    dp = defaultdict(set)

    for i in range(1, 9):
        dp[i].add(int(str(N) * i))  # NNN...N
        for j in range(1, i):
            for n1 in dp[j]:
                for n2 in dp[i - j]:
                    dp[i].add(n1 + n2)
                    dp[i].add(n1 - n2)
                    dp[i].add(n1 * n2)
                    if n2 != 0: dp[i].add(n1 // n2)  # 0으로 나눌 수 없음

        if number in dp[i]: return i # N을 i번 사용해서 number를 만들 수 있음

    return -1 # 최솟값이 8번보다 클 경우

유사 문제

• 가장 큰 수