[BOJ] 14395 - 4연산 (Python, JavaScript)

 

 

아이디어

 

BFS와 정렬로 s를 t로 바꾸는 최소 연산 방법을 구한다.

 

 

풀이 #1 (Python)

 

s와 t는 모두 1 이상이므로 수를 0으로 만드는 - 연산은 사용하지 않는다.

 

def solution():
    s, t = map(int, input().split())
    if s == t:
        print(0)
        return
    stack = [(t, '')]
    exps = []
    while stack:
        n, exp = stack.pop()
        if n == s:
            exps.append(exp)
            continue
        elif n == 1:
            exps.append('/'+exp)
            continue
        if int(n**0.5)**2 == n:
            stack.append((int(n**0.5), '*'+exp))
        if n%2 == 0:
            stack.append((n//2, '+'+exp))
    if exps:
        print(sorted(exps, key=lambda x: (len(x), x))[0])
    else:
        print(-1)

solution()

 

 

 

풀이 #2 (JavaScript)

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    const [s, t] = input[0].split(' ').map(Number);
    if (s === t) {
        console.log(0);
        return;
    }
    let stack = [[t, '']];
    let exps = [];
    while (stack.length) {
        const [n, exp] = stack.pop();
        if (n === s) {
            exps.push(exp);
            continue;
        }
        else if (n === 1) {
            exps.push('/'+exp);
            continue;
        }
        if (parseInt(n**0.5)**2 === n) stack.push([parseInt(n**0.5), '*'+exp]);
        if (n%2 === 0) stack.push([parseInt(n/2), '+'+exp]);
    }
    if (exps.length) console.log(exps.sort((a, b) => {
        if (a.length === b.length) return a < b ? -1 : 1;
        else return a.length-b.length;
    })[0]);
    else console.log(-1);
}

solution();