[BOJ] 15658 연산자 끼워넣기 2 - JAVA

1. 문제

15658번: 연산자 끼워넣기 (2)

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

 

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

---

2. 풀이

static 변수

int N	수의 개수
int[] num	수열
int[] operator	연산자 개수(+,-,*,/ 순서)
int MIN, MAX	최소, 최대값 = 출력할 수

 

Main

num, operator에 값을 저장한 후 dfs를 호출한다. 그 뒤에 MAX, MIN을 출력하면 된다.

dfs 파라미터로 첫번째 숫자와 1을 넣는다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   N = Integer.parseInt(in.readLine());
   StringTokenizer st = new StringTokenizer(in.readLine());
   num = new int[N];
   for(int i=0;i<N;i++) num[i] = Integer.parseInt(st.nextToken());

   st = new StringTokenizer(in.readLine());
   for(int i=0;i<4;i++) operator[i] = Integer.parseInt(st.nextToken());

   dfs(num[0],1);

   System.out.println(MAX+"\n"+MIN);
}

 

dfs

파라미터로 res, cnt를 받는다. res는 기존까지 계산 값, cnt는 현재 연산해야하는 수의 순서를 의미한다.

그래서 처음 main에서 dfs를 부를 때 res=num[0]과 cnt=1로 한 것이다.

cnt==N일 때 모든 계산이 끝난 것이므로 MAX, MIN값을 비교해서 저장한다.

연산자 하나씩 탐색하면서 남은 연산자가 있을 경우에만 재귀호출한다.

재귀호출 전 연산자 개수에서 1을 빼고, 재귀호출에서 돌아온 후 다시 1을 더한다.

public static void dfs(int res, int cnt){
   if(cnt==N){
      MIN = Math.min(MIN,res);
      MAX = Math.max(MAX,res);
      return;
   }

   for(int i=0;i<4;i++){
      if(operator[i]==0) continue;
      operator[i]-=1;
      switch(i){
         case 0:
            dfs(res+num[cnt],cnt+1);
            break;
         case 1:
            dfs(res-num[cnt],cnt+1);
            break;
         case 2:
            dfs(res*num[cnt], cnt+1);
            break;
         case 3:
            if(res<0) dfs(-((-res)/num[cnt]) ,cnt+1);
            else dfs(res/num[cnt],cnt+1);
            break;
      }
      operator[i]+=1;
   }
}

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_15658_연산자끼워넣기2 {
   static int N;
   static int[] num;
   static int[] operator = new int[4];//+-*/
   static int MIN = 1_000_000_001, MAX = -1_000_000_001;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(in.readLine());
      StringTokenizer st = new StringTokenizer(in.readLine());
      num = new int[N];
      for(int i=0;i<N;i++) num[i] = Integer.parseInt(st.nextToken());

      st = new StringTokenizer(in.readLine());
      for(int i=0;i<4;i++) operator[i] = Integer.parseInt(st.nextToken());

      dfs(num[0],1);

      System.out.println(MAX+"\n"+MIN);
   }
   public static void dfs(int res, int cnt){
      if(cnt==N){
         MIN = Math.min(MIN,res);
         MAX = Math.max(MAX,res);
         return;
      }

      for(int i=0;i<4;i++){
         if(operator[i]==0) continue;
         operator[i]-=1;
         switch(i){
            case 0:
               dfs(res+num[cnt],cnt+1);
               break;
            case 1:
               dfs(res-num[cnt],cnt+1);
               break;
            case 2:
               dfs(res*num[cnt], cnt+1);
               break;
            case 3:
               if(res<0) dfs(-((-res)/num[cnt]) ,cnt+1);
               else dfs(res/num[cnt],cnt+1);
               break;
         }
         operator[i]+=1;
      }
   }
}

---

3. 결과