[BOJ] 15658 - 연산자 끼워넣기 (2) (Python, JavaScript)

 

 

아이디어

 

DFS로 주어진 연산자로 가능한 식을 만들어 그 최댓값과 최솟값을 찾는다.

 

 

풀이 #1 (Python)

 

덧셈, 뺄셈, 곱셈, 나눗셈을 수행하는 람다식들을 리스트 cal에 저장한다.

리스트 operator에 각 연산자의 개수를 저장하고, 최댓값과 최솟값을 저장하는 리스트 res를 생성한다.

 

함수 dfs에서는 재귀 호출로 주어진 연산자를 사용하여 식을 만들고, 식을 모두 만들면 결과값과 비교하여 갱신해 나간다.

 

cal = [lambda a, b: a+b, lambda a, b: a-b, lambda a, b: a*b, lambda a, b: a//b if a > 0 else -(-a//b)]

def dfs(idx, total, a, s, m, d):
    global res
    if idx >= N:
        if total > res[0]:
            res[0] = total
        if total < res[1]:
            res[1] = total
        return
    if a > 0:
        dfs(idx+1, cal[0](total, A[idx]), a-1, s, m, d)
    if s > 0:
        dfs(idx+1, cal[1](total, A[idx]), a, s-1, m, d)
    if m > 0:
        dfs(idx+1, cal[2](total, A[idx]), a, s, m-1, d)
    if d > 0:
        dfs(idx+1, cal[3](total, A[idx]), a, s, m, d-1)

N = int(input())
A = list(map(int, input().split()))
operator = list(map(int, input().split()))
res = [-int(1e10), int(1e10)]
dfs(1, A[0], *operator)
print(res[0])
print(res[1])

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 같은 방식으로 동작한다.

나눗셈 결과를 parseInt 함수를 사용하여 정수 형태로 처리하며, res의 최댓값과 최솟값을 -Infinity와 Infinity로 초기화한다.

 

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

function dfs(idx, total, a, s, m, d) {
    if (idx >= N) {
        if (total > res[0]) res[0] = total;
        if (total < res[1]) res[1] = total;
        return;
    }
    if (a > 0) dfs(idx+1, total+A[idx], a-1, s, m, d);
    if (s > 0) dfs(idx+1, total-A[idx], a, s-1, m, d);
    if (m > 0) dfs(idx+1, total*A[idx], a, s, m-1, d);
    if (d > 0) dfs(idx+1, parseInt(total/A[idx]), a, s, m, d-1);
}

const N = Number(input[0]);
const A = input[1].split(' ').map(Number);
const operator = input[2].split(' ');
let res = [-Infinity, Infinity];
dfs(1, A[0], ...operator);
console.log(`${res[0]}`);
console.log(`${res[1]}`);

 

 

자바스크립트에서는 -0과 0이 구분되는데, 이 문제에서 계산 결과로 나오는 -0을 잘 처리하지 않아 많이 틀렸다.

템플릿 문자열과 parseInt 함수를 이용하여 -0을 출력하면 0이 출력된다.

그러나 parseInt 함수에 -0을 인자로 직접 넘기지 않고 -0이 나오는 계산식을 인자로 넘기면 -0이 출력된다.

`${-0}`; // 0
parseInt(-0); // 0
parseInt(-1/2); // -0
parseInt(1/-2); // -0

 

-0과 0은 구분되지만 서로 비교 연산을 수행하면 참이 나온다.

console.log(-0 === 0);  // true