문제 설명
아래와 같이 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번만 사용하여 표현할 수 있습니다.
내 풀이
def solution(N, number): result = [9] * 32001 # 1 result[N] = 1 arr = [set([]) for _ in range(9)] arr[1].add(N) for n in range(2, 9): if number == int(str(N)*n): return n if int(str(N)*n) <= 32000: arr[n] = {int(str(N)*n)} result[int(str(N)*n)] = n for k in range(1, n//2 + 1): for a in arr[n-k]: for b in arr[k]: arr[n].add(a+b) if a+b <= 32000: result[a+b] = min(n,result[a+b]) if a+b == number: return result[a+b] if 0 < a-b <= 32000: arr[n].add(a-b) result[a-b] = min(n,result[a-b]) if a-b == number: return result[a-b] elif 0 < b-a <= 32000: arr[n].add(b-a) result[b-a] = min(n,result[b-a]) if b-a == number: return result[b-a] if a*b <= 32000: arr[n].add(a*b) result[a*b] = min(n,result[a*b]) if a*b == number: return result[a*b] if 0 < a//b <= 32000: arr[n].add(a//b) result[a//b] = min(n,result[a//b]) if a//b == number: return result[a//b] elif 0 < b//a <= 32000: arr[n].add(b//a) result[b//a] = min(n,result[b//a]) if b//a == number: return result[b//a] arr[n] -= arr[n-1] arr[n] -= arr[n-2] return -1
정확성 테스트: ~10.95ms / 10.9MB
문제는 number에 사용된 N의 최소 횟수를 묻고 있다.
하지만 코드를 짤 때는 반대로 N을 n번 써서 만들 수 있는 어떤 숫자가 number와 일치할 때의 n을 return 할 것이다.
result의 인덱스에는 number가 들어가고 해당 인자의 값은 n이다.
모든 값을 9로 초기화 한 뒤에 더 적은 n이 등장하면 바꾸고 return 할 때에 여전히 9라면 대신 -1을 반환한다.
arr의 n번째 리스트에는 각 n에 대해 N을 n번 사용하여 만들 수 있는 숫자를 집합 형태로 담는다.
n이 1일 때 만들 수 있는 수는 N 밖에 없으므로 우선 result의 1번 요솟값으로 1을 담고 arr의 1번 어레이에 1을 추가한다.
이제 본격적으로 n이 2~8일 때를 따질 것이다.
N을 n번 반복하는 NN...N에 대해서 number가 NN...N, 즉 int(str(N)n)이라면 n을 반환하면 된다.
만약에 아니라면 그냥 arr[n]에 int(str(N)n)가 담긴 집합으로 초기화하고 result[int(str(N)*n)] = n으로 대입한다.
만약에 N을 n-k번 사용한 숫자와 k번 사용한 숫자 간의 사칙연산을 통해 얻은 숫자들은 N을 n번 사용해 사칙연산으로 만든 숫자들과 같다.
그래서 이를 for문을 통해 만드는데 계산을 2번 하는 것을 피하기 위해 k를 1에서 n//2까지로 잡을 것이다.
그 뒤로는 arr[n-k]와 arr[k]의 각 숫자 a, b를 덧셈, 뺄셈, 곱셈, 나눗셈 한 값을 arr[n]에 담고 기존 result 값과 비교해서 최솟값을 선택한다.
사칙연산을 할 때에는 조건이 필요한데
- 덧셈의 경우 arr에 담는 것은 조건이 필요 없다. 만약 이 수가 32000을 넘더라도 n번을 초과해 연산하는 경우 나눠서 32000 이하가 될 수 있기 때문이다. 다만 result에는 32000 이하일 때만 담는다.
- 뺄셈의 경우 양수가 되는 쪽을 선택한다. abs() 함수를 써도 될 것 같다.
- 곱셈은 1과 비슷하지만 어떤 수를 곱한 뒤에 나누는 것은 계산 횟수의 낭비이므로 arr에도 조건을 걸어준다.
- 나눗셈도 뺄셈과 비슷한데 작은 수에서 큰 수의 목을 구하면 0이므로 0보다 클 때에만 arr와 result에 담는다.
각각의 과정에서 number와 같다면 바로 return해 주자.
최악의 경우에(n이 9이상일 때) 계산 속도를 줄일 순 없지만 많은 경우 이로 인해 시간 단축이 될 것이다.
시간 단축을 위해 arr[n]과 arr[n-1]의 차집합, arr[n-2]과의 차집합을 해줬다.
return값은 최솟값을 원하므로 arr[n]에 포함된 수가 n보다 작은 인덱스의 arr 집합에도 포함돼 있다면 arr[n]에 포함된 숫자는 필요 없기 때문이다. 하지만 이 과정은 생략 가능하다.
이 모든 과정에서 return이 되지 않았다는 것은 최솟값이 8보다 크다는 것이므로 -1을 반환한다.
