아래와 같이 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 함수를 작성하세요.
cache
)을 만들어 준다. (인덱스 0은 사용하지 않는다.)i
라고 했을 때, cache[i]
에는 N을 i
번 사용했을 때 만들 수 있는 수들을 Set으로 모아서 저장한다.i==1
일 때는 만들 수 있는 수가 무조건 N밖에 없으므로 new Set([N])
을 저장해준다.i (i>1)
번 사용해서 만들 수 있는 수는 다음과 같은 과정으로 구한다.i
를 만들 수 있는 조합을 모두 만든다. (ex. i
가 3일 때, 모든 덧셈의 조합은 1+2, 2+1)i
를 1번 썼을 때 얻을 수 있는 수들과 2번 썼을 때 얻을 수 있는 수들을 cache
에서 얻기 위함이다.cache
의 각 원소는 내장객체 Set이므로, for ... of
구문을 통해 원소들을 순회할 수 있고, 이를 이중으로 반복해서 각 집합의 원소끼리의 모든 조합마다 사칙연산으로 만들어낸 모든 수들을 리턴받아 cache[i]
에 추가한다. cache[i]
에는 특별히 N을 i
번 이어붙여 만든 수도 추가해 주어야 한다.cache[i]
에 우리가 찾던 number가 포함되어 있다면 i
를 리턴한다. (Set.prototype.has()
함수를 통해 확인할 수 있다.)function getValues(x, y) {
return [x + y, x - y, x * y, Math.floor(x / y)];
}
function getMemoResult(cache, i, N) {
const ret = new Set();
ret.add(~~(N.toString().repeat(i)));
for(let a=1; a<i; a++) {
const beforeSet = cache[a];
const afterSet = cache[i-a];
for(let bef of beforeSet) {
for(let aft of afterSet) {
const values = getValues(bef, aft);
values.forEach(v => ret.add(v));
}
}
}
return ret;
}
function solution(N, number) {
const cache = Array(9);
if(N === number) return 1;
cache[1] = new Set([N]);
for(let i=2; i<=8; i++) {
cache[i] = getMemoResult(cache, i, N);
if(cache[i].has(number)) return i;
};
return -1;
}
def getCalcs(x, y):
if y!=0:
return [x+y, x-y, x*y, x//y]
else:
return [x+y, x-y, x*y]
def getCombination(number):
ret = []
for i in range(1, number + 1):
ret.append((i, number-i))
return ret
def solution(N, number):
cache = [set() for _ in range(10)]
cache[1].add(N)
answer = -1
if number == N:
return 1
def memo(index):
nonlocal answer
if index == 9:
return
combinations = getCombination(index)
for index1, index2 in combinations:
setOne = cache[index1]
setTwo = cache[index2]
for s1 in setOne:
for s2 in setTwo:
cache[index].update(getCalcs(s1, s2))
repeated = int(str(N)*index)
cache[index].add(repeated)
if number in cache[index]:
answer = index
for i in range(2, 10):
memo(i)
if answer != -1:
break
#정답 리턴
return answer