14888번: 연산자 끼워넣기 (acmicpc.net)
알고리즘 : dfs
- Javascript
/**
* 제출용. 아래 로컬용을 지우고 제출하자.
*/
// let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
/**
* 로컬용, 예제.txt를 생성해서 예제를 복붙하자.
*/
function solution() {
let input = require("fs")
.readFileSync("input.txt") //"/dev/stdin"
.toString()
.split("\n")
.map((val) => val.trim());
let n = +input.shift();
let a = input
.shift()
.split(" ")
.map((v) => +v);
let operator = input
.shift()
.split(" ")
.map((v) => +v);
const cal = (idx, a, b) => {
if (idx === 0) return a + b;
else if (idx === 1) return a - b;
else if (idx === 2) return a * b;
else return parseInt(a / b);
};
let oper = [];
// dfs?
let min = Number.MAX_SAFE_INTEGER;
let max = Number.MIN_SAFE_INTEGER;
const dfs = (cnt) => {
if (cnt === n - 1) {
let num = a[0];
for (let i = 0; i < oper.length; i++) {
num = cal(oper[i], num, a[i + 1]);
}
if (num > max) max = num;
if (num < min) min = num;
}
for (let i = 0; i < 4; i++) {
if (!operator[i]) continue;
operator[i]--;
oper.push(i);
dfs(cnt + 1);
operator[i]++;
oper.pop();
}
};
dfs(0);
console.log([max, min].join("\n"));
}
solution();
- Python
import sys
sys.stdin = open("baekjoon/14888/input.txt","r")
input = sys.stdin.readline
n=int(input())
numbers = list(map(int,input().split()))
operator = list(map(int,input().split()))
maxN = -1e10
minN = 1e10
oper = []
def cal (idx,a,b):
if idx==0:
return a+b
elif idx==1:
return a-b
elif idx==2:
return a*b
else:
if a<0:
return -(-a//b)
else:
return a//b
def dfs (cnt):
global maxN,minN
if cnt==n-1:
num = numbers[0]
for i in range(len(oper)):
num = cal(oper[i],num,numbers[i+1])
if num>maxN:
maxN=num
if num<minN:
minN=num
return
for i in range(4):
if not operator[i]:
continue
operator[i]-=1
oper.append(i)
dfs(cnt+1)
oper.pop()
operator[i]+=1
dfs(0)
print(maxN)
print(minN)
'코딩테스트(알고리즘) > baekjoon' 카테고리의 다른 글
[baekjoon] 3190 뱀 (Javascript,Python) (0) | 2023.03.15 |
---|---|
[baekjoon] 14499 주사위 굴리기 (Javascript,Python) (0) | 2023.03.14 |
[baekjoon] 1520 내리막 길 (Javascript,Python) (0) | 2023.03.03 |
[baekjoon] 1987 알파벳 (Javascript,Python) (0) | 2023.03.02 |
[baekjoon] 13023 ABCDE (Javascript, Python) (0) | 2023.02.27 |