❓문제 설명
- 아래와 같이 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 합니다.
📌 풀이
N을i번 사용해서 만들 수 있는 수의 개수의 규칙을 알아내면 된다.- 먼저
N을1번 이용하는 수들의 집합 부터i-1번 이용하는 수들의 집합 까지 구한다.- 이 집합들 에서
k번 사용하는 경우와i-k번 사용하는 경우의 집합의 숫자를 꺼내서 사칙연산을 수행하면N을i번 사용해서 만들 수 있는 수 들을 구할 수 있다.- 이러한 과정은
i라는 큰 문제를k,i-k와 같은 작은 문제로 나누어서 해결하고, 또 그 안에k를 다시 작은 문제로 나누어서 해결하는 방식으로 풀 수 있기 때문에 Dynamic Programming을 이용하여 문제를 해결하면 된다.
<구현>
def solution(N, number):
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 