N으로 표현
문제
아래와 같이 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 number return
5 12 4
2 11 3
풀이
규칙을 찾아내는 것이 중요하다. 위 규칙을 이용해 5로 만들 수 있는 숫자를 구해보자. 사칙연산 중 나누기의 나머지는 무시한다.
N = 1일 때, 5
N = 2일 때, 5+5 5-5 5*5 5/5, 55
N = 3일 때, 5+(5+5) 5-(5+5) 5*(5+5) 5/(5+5) 5+55
N = 4일 때, 5+(5+(5+5)) 5-(5-(5+5)) … (5+5)+(5+5) (5+5)-(5+5) …
N=4 은 N=1과 N=3의 경우의 수 모두를 각각 사칙연산하고, N=2과 N=2의 경우의 수 모두를 각각 사칙연산한 것이다. 이 규칙대로라면 N=5 은 N=1과 N=4의 경우의 수, N=2과 N=3의 경우의 수 모두를 각각 사칙연산한 것이다.
- N_i을 만든다. N_i[1]은 N=1인 경우의 수, N_i[2]은 N=2인 경우의 수를 담아 둔 것이다.
- N=4은 1+3, 2+2로 만들고 N=5은 1+4, 2+3로 만들고 N=6은 1+5, 2+4, 3+3로 만드는 loop을 만든다.
- N_i[n]을 통해 앞에 저장해둔 경우의 수를 꺼내와 연산할 수 있다.
- 각 사칙연산을 계산하고 tmp라는 list에 집어넣고 모두 계산이 끝나면 N_i에 넣는다.
def solution(N, number):
# 1개만 사용해서 표현가능 할 때
if N == number:
return 1
# N=i 일 때 경우의 수
N_i = []
N_i.append([N]) # N=1 입력
for n in range(2, 9):
# n까지 숫자 중 절반까지만 계산
tmp = []
tmp.append(int(str(N)*n))
for i in range(1, n//2+1):
# 더해서 N을 만들 수 있는 수 (4=3+1, 4=2+2)
for y in N_i[i-1]:
for x in N_i[n-i-1]: # 빼기와 나누기는 앞뒤 관계 영향 O
tmp.append(y+x)
tmp.append(y-x)
tmp.append(x-y)
tmp.append(x*y)
if x != 0:
tmp.append(y//x)
if y != 0:
tmp.append(x//y)
if number in tmp:
return n
N_i.append(tmp)
return -1