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
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.
# N : 사용할 수 있는 숫자
# number : N을 통해서 만들 수 있는 결과 값
def solution(N, number) :
# 주어진 숫자 (N)을 사용해서 나올 수 가능 한 숫자들, result_set[3] 는 N을 가지고
# 3번 사용해서 나올 수 있는 숫자들
# 처음에는 N을 한번만 사용해서 나올 수 있는 숫자들 => N
result_set = [0,[N]]
if N == number :
return 1
for i in range(2, 9) :
case_set = []
firstnum = int(str(N)*i)
case_set.append(firstnum)
for j in range(1, i//2+1):
for x in result_set[j]:
for y in result_set[i-j]:
case_set.append(x+y)
case_set.append(x - y)
case_set.append(y-x)
case_set.append(x * y)
if y != 0:
case_set.append(x/y)
if x != 0:
case_set.append(y/x)
if number in case_set:
return i
result_set.append(case_set)
return -1** 해결 방법:
주어진 숫자 N으로 각 횟수당 만들수 있는 숫자 조합을 만든다.
만들어진 숫자 조합에 number로 주어진 숫자가 있는지 확인한다.
만약 있다면 그 시점에서의 횟수를 답으로 리턴한다.
없다면 횟수를 하나 늘리고 가능한 숫자 조합을 만들고 1~3을 반복한다.
*** N이 1개 인 조합 => N
N이 2개 인 조합 => 2가지 경우(NN), (N+N, N-N, N/N,.. 사칙연산)
...
=>
N이 2인 숫자 조합을 만들기 위해서는 N이 1일때 경우의 수와 N이 1일때 경우의 수를 각각 사칙연산했다
N이 3인 숫자 조합을 만들기 위해서는 N이 1일때 경우의 수와 N이 2일때 경우의 수를 각각 사칙연산했다.
N이 4인 숫자 조합을 만들기 위해서는 N이 1일때 경우의 수와 N이 3일때, N이 2일때 경우의 수와 N이 2일때,경우의 수를 각각 사칙연산했다.** 결국 4중 for문을 사용하여 품
먼저 N의 사용갯수가 어떻게 되느냐에 따라
-for i in range(2, 9)
개수에 따라 그 개수를 맞출 수 있는 경우의 수
- for j in range(1, i//2+1)
그리고 마지막으로 그 개수를 맞출 수 있는 경우의 수에서 두개의 리스트의 원소들을 서로 사칙연산해서 결과 도출
- for x in result_set[j]:
for y in result_set[i-j]:
