문제 링크
풀이 과정
•
사칙연산의 수행 순서 및 연산자에 따라, 연산의 결과가 다릅니다. 또한, 이를 아우르는 경우의 수는 무수하게 많을 것입니다.
•
언뜻 문제를 봤을 때, 쉽사리 문제의 풀이 방법이 떠오르지 않을 수 있습니다.
•
이런 순간에는, 제한 사항에 문제를 풀 수 있는 실마리가 있는 지 확인하는 과정이 필요합니다.
◦
숫자 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번보다 클 경우
Python
복사