문제
숫자 N과 사칙연산만을 이용하여 number를 표현하라.
가능한 방법중 N을 가장 적게 사용하용하는 값을 반환하라.
ex) 12 = (55+5)/5 주어지는 숫자 : N
만들고자 하는 수 : number
N은 1이상 9 이하
number는 1이상 32,000 이하
나누기 연산의 나머지는 무시
최솟값이 8보다 크면 -1 리턴
입출력 예시
| N | number | return |
|---|---|---|
| 5 | 12 | 4 |
| 2 | 11 | 3 |
접근
DP 문제이다.
주어지는 수 N을 1번만 사용한 경우부터 8번사용한 경우까지 찾아나가며 답이 없는 경우 -1을 리턴한다.
예를 들어 N이 2일 때, 한번 사용하는 경우는 {2} 한 가지 경우 뿐이다.
두 번부터는 이전의 연산 결과들을 이용한다.
두 번사용한 경우는 {22}와 한번 사용한 결과를 사칙연산한 경우들이 추가된다.
\(S[1] = {2}\)
\(S[2] = {22}, S[1] +-*/ S[1]\)
\(S[3] = {222}, S[2], S[1] +-*/ S[1], [2] ...\)
이런식으로 모든 조합을 탐색하면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(N, number):
answer = -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(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
return answer