연산자 끼워넣기 (2)

문제

언어

  • JavaScript

순서도

  1. 연산자의 각 개수를 저장
  2. 주어진 연산자로 만들 수 있는 모든 경우 만들기
  3. 만든 각 경우와 수열을 조합해서 결과를 출력하고, 그 중에서 최댓값과 최솟값 출력

문제 풀이 step 1

  • 백준 14888번 - 연산자 끼워넣기 풀이 의 방법을 이용하면 똑같이 풀 수 있는 문제입니다.
  • N 개의 수로 이루어진 수열과 수와 수 사이에 끼워넣을 수 있는 N - 1 개의 연산자가 주어집니다.
  • 이 때, 수열과 연산자를 이용해서 만들 수 있는 모든 식을 만들어보고 그 결과값들 중에서 최댓값과 최솟값을 찾는 문제입니다.
  • 우선, 주어진 연산자들의 개수를 세어줍니다.
  • 재귀함수를 이용해서 주어진 연산자들로 만들 수 있는 모든 경우를 만듭니다.
  • 그리고 주어진 수에 위에서 만든 연산자들의 조합을 연결해서 결과값을 도출합니다.
  • 결과값들 중에서 최댓값과 최솟값을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드 1

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

// 최솟값과 최댓값 초기화
let min = 1000000000;
let max = -1000000000;

// 주어진 연산자로 만들 수 있는 모든 경우 만들어보는 재귀 함수
const rec = (n, arr, plus, sub, mul, div, num, depth) => {
	if (depth === n) {
		min = Math.min(min, num);
		max = Math.max(max, num);
		return;
	}

	// 각 연산자의 개수를 이용해서 재귀함수를 호출
	// 각 재귀함수는 한번 호출할 때마다 현재 가지고 있는 연산자를 하나 사용하는 방식으로 동작
	// 호출과 동시에 연산을 수행해서 그 값을 재귀함수의 매개변수로 넣어줌
	// ex) res + nums[depth + 1]
	if (plus > 0)
		rec(n, arr, plus - 1, sub, mul, div, num + arr[depth], depth + 1);
	if (sub > 0)
		rec(n, arr, plus, sub - 1, mul, div, num - arr[depth], depth + 1);
	if (mul > 0)
		rec(n, arr, plus, sub, mul - 1, div, num * arr[depth], depth + 1);
	if (div > 0)
		rec(n, arr, plus, sub, mul, div - 1, parseInt(num / arr[depth]), depth + 1);
};

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);
	const [plus, sub, mul, div] = input[2].split(" ").map(Number);

	rec(n, arr, plus, sub, mul, div, arr[0], 1);

	// 최댓값과 최솟값 출력
	return max + "\n" + min;
};

console.log(solution(input));