문제

아래와 같이 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 합니다.

풀이

• 동적 계획법(Dynamic Programming)을 이용한다.
  • N을 한 번만 사용했을 때 만들 수 있는 수의 집합,
  • N을 두 번 사용했을 때 만들 수 있는 수의 집합,
  • N을 세 번 사용했을 때 만들 수 있는 수의 집합, ...
  • 이때 각 단계는 이전 단계들의 조합으로 구해낼 수 있다.
• 최솟값이 8보다 크면 -1을 return하라고 했으므로 총 크기 9의 배열(cache)을 만들어 준다. (인덱스 0은 사용하지 않는다.)
  • 각 인덱스를 i라고 했을 때, cache[i]에는 N을 i번 사용했을 때 만들 수 있는 수들을 Set으로 모아서 저장한다.
  • i==1일 때는 만들 수 있는 수가 무조건 N밖에 없으므로 new Set([N])을 저장해준다.
  • 이후의 인덱스부터는 다음 알고리즘을 수행한다.

알고리즘

• 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() 함수를 통해 확인할 수 있다.)
• 특수케이스) N과 number가 같으면 1을 리턴한다.

코드

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