백준 14888 : 연산자 끼워넣기

💡기본 정보

유형
: 시뮬레이션
풀이 날짜
: 2025년 01월18일 
풀이방법 한줄 요약
: 백트래킹으로 모든 가능한 연산자 조합을 탐색해 최댓값과 최솟값 찾기 

 

💡문제에서 구해야 할 것

N개의 수로 이루어진 수욜이 주어지고 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어짐
연산자는 덧셈, 뺄셈, 곱셈, 나눗셈 으로만 이루어짐
우리는 수와 수 사이에 연산자를 하나씩 넣어서 수식을 하나 만들 수 있음 이 때 주어진 수의 순서를 바꾸면 안됨
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행, 또한 나눗셈은 정수 나눗셈으로 몫만 취함
음수를 양수로 나눌 때는 양수로 바꾼 뒤 몫을 취하고 그 몫을 음수로 바꾼 것과 같음 

N개의 수가 N-1개의 연산자가 주어졌을 때 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성
- 입력 : 첫째 줄에 수의 개수 N이 주어짐(2<=N<=11) 
            둘째 줄에 A1,A2,...,An이 주어짐 (1<=Ai<=100)
            셋째 줄에는 합이 N-1인 4개의 정수가 주어짐 . 차례대로 덧셈의 개수, 뺄셈의 개수, 곱셈의 개수, 나눗셈의 개수
  출력 : 첫째 줄에 만들 수 있는 식의 결과의 최댓값
           둘째 줄에는 최솟값을 출력
           연산자를 어떻게 끼워 넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어짐 
           또한 앞에서부터 계산했을 때 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고 10억보다 작거나 같음 

 

💡알고리즘 설계

- 백트래킹으로 가능한 모든 연산 순서를 탐색

- 모든 연산자 조합을 탐색해 최댓값과 최솟값 출력 

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0,"utf8").toString().split("\n");
const N = parseInt(input[0]);
const An = input[1].split(" ").map(Number);
const cal = input[2].split(" ").map(Number);

const calculator = [
    (a, b) => a + b,
    (a, b) => a - b,
    (a, b) => a * b,
    (a, b) => parseInt(a / b),
  ];

function calculate() {
  let Max = Number.MIN_SAFE_INTEGER;
  let Min = Number.MAX_SAFE_INTEGER;

  function dfs(count, result) {
    if (count === N - 1) {
      Max = Math.max(Max, result);
      Min = Math.min(Min, result);
      return;
    }

    for (let i = 0; i < cal.length; i++) {
      if (cal[i] === 0) continue;

      cal[i]--;
      dfs(count + 1, calculator[i](result, An[count + 1]));
      cal[i]++;
    }
  }
dfs(0, An[0]);
return [Max,Min];
}
const answer = calculate();
if (answer) {
  console.log(answer.join("\n"));
}

 

💡시간복잡도

💡 틀린 이유 & 틀린 부분 수정

백트래킹으로 푼다는 사실을 몰라서 틀렸음

 

💡 다른 풀이 or 기억할정보

백트래킹
: 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것